{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_lhcu-eFro6f"
   },
   "source": [
    "# 第14章聚类方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.聚类是针对给定的样本，依据它们属性的相似度或距离，将其归并到若干个“类”或“簇”的数据分析问题。一个类是样本的一个子集。直观上，相似的样本聚集在同类，不相似的样本分散在不同类。\n",
    "\n",
    "2.距离或相似度度量在聚类中起着重要作用。\n",
    "\n",
    "常用的距离度量有闵可夫斯基距离，包括欧氏距离曼哈顿距离、切比雪夫距离、、以及马哈拉诺比斯距离。常用的相似度度量有相关系数、夹角余弦。\n",
    "用距离度量相似度时，距离越小表示样本越相似；用相关系数时，相关系数越大表示样本越相似。\n",
    "\n",
    "3.类是样本的子集，比如有如下基本定义：\n",
    "用$G$表示类或簇，用$x_i$,$x_j$；等表示类中的样本，用$d_{ij}$表示样本$x_i$与样本$x_j$之间的距离。如果对任意的$x _ { i } , x _ { j } \\in G$，有$$d _ { i j } \\leq T$$\n",
    "则称$G$为一个类或簇。\n",
    "\n",
    "描述类的特征的指标有中心、直径、散布矩阵、协方差矩阵。\n",
    "\n",
    "4.聚类过程中用到类与类之间的距离也称为连接类与类之间的距离包括最短距离、最长距离、中心距离、平均距离。\n",
    "\n",
    "5.层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中层次聚类又有聚合或自下而上、分裂或自上而下两种方法。\n",
    "\n",
    "聚合聚类开始将每个样本各自分到一个类；之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件；得到层次化的类别。分裂聚类开始将所有样本分到一个类；之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件；得到层次化的类别。\n",
    "\n",
    "聚合聚类需要预先确定下面三个要素：\n",
    "\n",
    "（1）距离或相似度；\n",
    "（2）合并规则；\n",
    "（3）停止条件。\n",
    "\n",
    "根据这些概念的不同组合，就可以得到不同的聚类方法。\n",
    "\n",
    "6.$k$均值聚类是常用的聚类算法，有以下特点。基于划分的聚类方法；类别数k事先指定；以欧氏距离平方表示样本之间的距离或相似度，以中心或样本的均值表示类别；以样本和其所属类的中心之间的距离的总和为优化的目标函数；得到的类别是平坦的、非层次化的；算法是迭代算法，不能保证得到全局最优。\n",
    "\n",
    "$k$均值聚类算法，首先选择k个类的中心，将样本分到与中心最近的类中，得到一个聚类结果；然后计算每个类的样本的均值，作为类的新的中心；重复以上步骤，直到收敛为止。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "hGPg5M7wsOQY"
   },
   "source": [
    "### 层次聚类 \n",
    "\n",
    "1. **聚合**（自下而上）：聚合法开始将每个样本各自分裂到一个类，之后将相距最近的两类合并，建立一个新的类，重复次操作知道满足停止条件，得到层次化的类别。\n",
    "\n",
    "2. **分裂**（自上而下）： 分裂法开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件，得到层次化的类别。\n",
    "\n",
    "\n",
    "### k均值聚类\n",
    "\n",
    "k均值聚类是基于中心的聚类方法，通过迭代，将样本分到k个类中，使得每个样本与其所属类的中心或均值最近，得到k个平坦的，非层次化的类别，构成对空间的划分。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "qAlQYJ2Srd2_"
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "import numpy as np\n",
    "from sklearn import datasets,cluster\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "M_XOaWU5xpjI"
   },
   "outputs": [],
   "source": [
    "iris = datasets.load_iris()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 143
    },
    "colab_type": "code",
    "id": "_swSYxCr0RzU",
    "outputId": "88d09d3b-7700-4af5-e3b6-4d7735a3dd75"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\n",
       "       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\n",
       "       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gt = iris['target'];gt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "UoIRpftd9Uh2"
   },
   "source": [
    "3类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "pI6cS2sjy3Sz",
    "outputId": "3d9d01de-31b4-4eea-989c-b0a986a77af5"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(150, 2)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iris['data'][:,:2].shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "YwIVX5j81348"
   },
   "outputs": [],
   "source": [
    "data = iris['data'][:,:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "h-wEZbDR03E_"
   },
   "outputs": [],
   "source": [
    "x = data[:,0]\n",
    "y = data[:,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 269
    },
    "colab_type": "code",
    "id": "bW_lxjVdy4rW",
    "outputId": "ded2fc31-a69a-4e40-b0d4-350b995488ce"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAdAElEQVR4nO3df4wc9Znn8ffHMyYEkphTmNsAxjanZDciCwQYEXxerdiMb0UCC3+E03rliB9KNLc2uZC7XUXHWiKxJe8p0mnDZRFmJ8ne4sAm5NgkZ34kF3A2CuEurMaEHyHkJC7Bxgt7TCAZjnOOw+a5P7pndqbdM1U99e3qqq7PSxrRXVVT/dS3i2fa/XzrKUUEZmY2/FYNOgAzMyuHE76ZWUM44ZuZNYQTvplZQzjhm5k1hBO+mVlD5Er4kp6V9KSkxyRNd1kvSZ+T9IykJyRdkD5UMzMrYrSHbX8nIn6+xLoPAO9q/7wP2NP+r5mZVUSqr3SuBPZGyw+AUySdlmjfZmaWQN5P+AF8W1IAfxERUx3rzwCeW/D8cHvZCws3kjQJTAKcfPLJF7773e9eUdBmZk114MCBn0fE2Ep+N2/C3xQRz0v6p8ADkn4SEd9bsF5dfue4ng3tPxRTAOPj4zE9fVw5wMzMliHp4Ep/N9dXOhHxfPu/LwJfBy7q2OQwcOaC52uB51calJmZpZeZ8CWdLOmtc4+B3wV+1LHZPuDq9mydi4HZiHgBMzOrjDxf6fwa8HVJc9v/dUR8S9IfAkTEbcD9wAeBZ4AjwHX9CdfMzFYqM+FHxE+B87osv23B4wCuTxuamZml5CttzcwawgnfzKwhnPDNzBrCCd/MrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCGc8M3MGsIJ38ysIXInfEkjkn4o6d4u666VNCPpsfbPR9OGaWZmReW5ifmcG4Cngbctsf6uiPhY8ZDMzKwfcn3Cl7QWuAz4Qn/DMTOzfsn7lc7NwCeBN5bZ5kOSnpB0t6Qzi4dmZmYpZSZ8SZcDL0bEgWU2uwfYEBHnAg8Cty+xr0lJ05KmZ2ZmVhSwmZmtTJ5P+JuAKyQ9C3wFeL+kOxZuEBEvRcRr7aefBy7stqOImIqI8YgYHxsbKxC2mZn1KjPhR8SNEbE2IjYAW4DvRMSHF24j6bQFT6+gVdw1S+bOJ+9kw80bWLVzFRtu3sCdT9456JDMaqeXWTqLSNoFTEfEPuDjkq4AjgIvA9emCc+slewn75nkyOtHADg4e5DJeyYB2HrO1kGGZlYrioiBvPD4+HhMT08P5LWtXjbcvIGDswePW75+zXqe/cSz5QdkNkCSDkTE+Ep+11faWuUdmj3U03Iz684J3ypv3Zp1PS03s+6c8K3ydk/s5qTVJy1adtLqk9g9sXtAEZnVkxO+Vd7Wc7Yy9XtTrF+zHiHWr1nP1O9NuWBr1iMXbc3MasRFWzMzy+SEb2bWEE74ZmYN4YRvpXBrBLPBW3FrBbO83BrBrBr8Cd/6bsf+HfPJfs6R14+wY/+OAUVk1kxO+NZ3bo1gVg1O+NZ3bo1gVg1O+Nb3gqpbI5hVgxN+w80VVA/OHiSI+YJqyqTv1ghm1eDWCg3nXvNm9eLWCrZiLqiaNYcTfsO5oGrWHE74DeeCqllz5E74kkYk/VDSvV3WvUnSXZKekfSIpA0pg7T+GaaCqts3mC2vl9YKNwBPA2/rsu4jwC8i4p2StgCfAX4/QXxWgq3nbK1lgl/I7RvMsuX6hC9pLXAZ8IUlNrkSuL39+G5gQpKKh2eWj9s3mGXL+5XOzcAngTeWWH8G8BxARBwFZoG3d24kaVLStKTpmZmZFYRr1p1nG5lly0z4ki4HXoyIA8tt1mXZcRP8I2IqIsYjYnxsbKyHMM2W59lGZtnyfMLfBFwh6VngK8D7Jd3Rsc1h4EwASaPAGuDlhHFahW2/bzuju0bRTjG6a5Tt920vPQbPNjLLlpnwI+LGiFgbERuALcB3IuLDHZvtA65pP76qvc1gLuG1Um2/bzt7pvdwLI4BcCyOsWd6T+lJf5hmG5n1S0+tFSRdAvxxRFwuaRcwHRH7JJ0IfAk4n9Yn+y0R8dPl9uXWCsNhdNfofLJfaEQjHL3p6AAiMhtuRVor9HTHq4j4LvDd9uObFiz/v8C/XEkAVm/dkv1yy81scHylrRUyopGelpvZ4DjhWyGTF072tNzMBscJf8ht3rsZ7dT8z+a9m5Pu/9bLbmXb+Lb5T/QjGmHb+DZuvezWpK/jtglWZSnOzzLOcffDH2Kb925m/8/2H7d84qwJHrz6wQFEtDKdbROgNeXSs3CsClKcn73so0jR1gl/iGnn0t0t4lP1mTXrm7RYlaU4P3vZh2+AYkPNbROsylKcn2Wd4074Vnlum2BVluL8LOscd8IfYhNnTfS0fClZxaR+F5vcNsGqLMX5WdY57oQ/xK47/zrU0ddOiOvOvy73PuaKSQdnDxLEfJ/5uaSetT4Ft02wKktxfpZ1jrtoO8TKKCa5oGpWLhdtrasyikkuqJrVhxP+ECujmOSCqll9OOGvUFlXfhYpmJZRTHJB1frJV1in1VO3TGsp64bZWa+TtX4ulh37d3Bo9hDr1qxj98TunotJy+0jxWuYdeMb06fnou0KlFWodMHUmsznd3cu2pasrEKlC6bWZD6/03PCX4GyCpUumFqT+fxOzwl/BcoqVLpgak3m8zu9zIQv6URJfyfpcUlPSdrZZZtrJc1Ieqz989H+hFsNZV0Vl/U6W8/Zysa1Gxf9zsa1GxfFsf2+7YzuGkU7xeiu0a43Fy9jJoRnW1ivfIV1eplFW0kCTo6IVyWtBr4P3BARP1iwzbXAeER8LO8L17loWxXb79vOnuk9xy2fuwFJ1noop9e8+9mbpdPXom20vNp+urr9U59m6kNs6sDUssuz1kNrOuXCRAxw5PUj7Ni/I1GU5byGmWXL9R2+pBFJjwEvAg9ExCNdNvuQpCck3S3pzCX2MylpWtL0zMxMgbAN4FgcW3Z51nooZyaEZ1uYVUOuhB8RxyLivcBa4CJJv9mxyT3Ahog4F3gQuH2J/UxFxHhEjI+NjRWJ22D+PrJLLc9aD+XMhPBsC7Nq6GmWTkT8EvgucGnH8pci4rX2088DFyaJrsJSFCHzFFSXM3nh5LLLs9ZDaybE6lWrF61fvWp1TzMhso6jTrMtir6veX7fBWwblDyzdMYkndJ+/GZgM/CTjm1OW/D0CuDplEFWTYoe8HMF1YVfv+yZ3tNz0l/OpnWbGF21uHvG6KpRNq3btGhZqy6/9PPl5DmOusy2KPq+5vn9Mu4fYLaUPLN0zqX1Fc0IrT8QX42IXZJ2AdMRsU/Sv6eV6I8CLwPbIuInS+6Ues/SSXHJ9+iu0a7fsY9ohKM3HU2yjzxxFj2WFMdRFUXHoozxNisySyezeVpEPAGc32X5TQse3wjcuJIA6ihFETJPQbXoPvLEWfRYUhxHVRQdizLG26wIX2m7AimKkHkKqkX3kSfOoseS4jiqouhYlDHeZkU44a9AiiJknoJq0X3kibPosaQ4jqooOhZljLdZEU74K5CiCHnrZbeybXzboimUC6+AzbuPibMmFi2bOGtifh9bz9nKNedds+g1rjnvmkVxFj2WFMdRFUXHIs/v52mHUYaiM8SsntwPv8ayWha4pUH15Gl30YQYbOWKFG2d8GvMN0ipnyrMaqpCDLZyvgFKQ/kGKfVThVlNVYjBBsMJv8Z8g5T6qcKspirEYIPR2IRfxiX0/S6M7Z7YzQkjJyxadsLICb5ByhKq0NIgz6ymrPOm6HHknVmV9TpF1+dRhfdsmGReeDWMOouZc5e3A7mKmXl+v7MwNtdyAEhaGOuswSx8PhfLjv07ODR7iHVr1rF7YncjC7ZF3/NU5t77qQNTHItjjGiEyQsn55dnnTcpjiMrBsger6Lr86jKezZMGlm0LeMS+jIKYy7K5leXsUrRLiOFohMCUsRZl/esbC7a9qiMS+jLKIy5KJtfXcYqRbuMFIpOCEgRZ13eszppZMIv4xL6MgpjLsrmV5exStEuI4WiEwJSxFmX96xOGpnwy7iEvoyWAy7K5leXsUrRLiOFrNcpuj5FDLYCETGQnwsvvDAG6Y4n7oj1n10f+rRi/WfXxx1P3NHT72+7d1uM7BwJPk2M7ByJbfdu63mbPDGk2Ie11GWsJm6fCD7N/M/E7ROL1qc4jqzXyPM6Z99y9qJ9nH3L2cnjrMt7ViZabelXlHcbWbQtKkXLgjz78CXwzVNGO4zNezez/2f7j1s+cdYED179YGn7sJVxa4WSlTUDwZfAN08ZM1O0c+k7msWn8uWDFPuwlfEsnZKVNQPBl8A3j2emWD854a9AWTMQfAl883hmivVTnpuYnyjp7yQ9LukpSTu7bPMmSXdJekbSI5I29CPYvPJcjl3kku1UMxA6E/eIRnqe6VOFS89TxNDvdgJ5XiPP65TRLiPr3Nq8dzPaqfmfzXs393QcnfdQWGp5in1kKaM9Qwp1iTNLnk/4rwHvj4jzgPcCl0q6uGObjwC/iIh3Ap8FPpM2zPzmil4HZw8SxPzl2AvfgDzbLCfFDVAePvTwcV/NHItjPHzo4fnnm9ZtYlXHW7SKVWxatynJcaSQIoa54vTceMy1E5hLpmW8Rp7XybOPorLOrW7F0v0/278o6Wcdx6+//de7vvbC5Vn7ePDqB7vefKeXgm3Wa1Th/K5TnHn0VLSVdBLwfWBbRDyyYPl/BT4dEf9d0ijwD8BYLLPzfhVt8xS9qnDJdp6CbB363aeIoYx2AinGuwpF9DzF0hTHUca5VYfzG6oXZ9+LtpJGJD0GvAg8sDDZt50BPAcQEUeBWeDtXfYzKWla0vTMzMxK4s2Up+hVhcJYnoJsHfrdp4ihjHYCKca7LkX0FMdRxrlVh/M7TxxViTOPXAk/Io5FxHuBtcBFkn6zY5NuHzuO+3QfEVMRMR4R42NjY71Hm0OeolcVCmN5CrJ16HefIoYy2gmkGO+6FNFTHEcZ51Ydzu88cVQlzjx6mqUTEb8Evgtc2rHqMHAmQPsrnTXAywni61meolcVLtnOU5At4/L1olLEUEY7gRTjXUa7jCx5iqUpjqOMc6sO53eeOKoSZy5Zl+ICY8Ap7cdvBh4CLu/Y5nrgtvbjLcBXs/bbz9YKKVoWlCFPDFnHUoVLz8u41D/F+5WiHUaKtgdF39M8bRGyjiPFuZdC0bEo6/yvShwRfW6tIOlc4HZghNa/CL4aEbsk7Wq/8D5JJwJfAs6n9cl+S0T8dLn9DvJK2zIuX7f8st6Pst6vonHkibOMY23K+d2U4+zk1go9qkr131qqMguijJt++MYh6TTlODu5tUKP6lRVb4KqzIIo46YfvnFIOk05zpQamfDrVFVvgqrMgijjph++cUg6TTnOlBqZ8GtVVW+A3RO7Wb1q9aJlq1etXjQLIqsNBRS/vD3PbIxuVz4vXL/cceQ91uVeI89xpjq/q94uIO9xlnEcVR+rOY1M+ClaI1hakpZ8nqcNRYrL27POi4cPPcwbvLHod97gjUVxLHcceY91udfIc5wpzu86tAvIc5xlHEcdxmpOI4u2Vi11aQWQogVE0WOtSgG7LqrQIiI1F22t1urSCiBFC4iix1qVAnZdVKFFRJU44dvA1aUVQIoWEEWPtSoF7LqoQouIKnHCt4EXnHZP7OaEkRMWLTth5ISeWwEste9eLDcWKVpAFD3WsiYcDMvEhiq0iKgSJ/yGq0rBqbOWtPD5rZfdyrbxbfOfckc0ctyN3P/0e3/adb9LLe8mayyy4shbLF3uWLPugVDWhINhmdhQxnHUaaxctG24KhTnUsSQ4qbaVSjwVeH9sGpz0dZWrAoFpyrEUFYcVbmq2JrJCb/hqlBwqkIMZcVRlauKrZmc8BuuCgWnFDGcferZPS3vVxxFX6MK74cNLyf8hiur4LTc7Je8V0wuN5Poqeuf4vS3nL5o2elvOZ2nrn8qd4wp4ij6GnUqANo/GvRMt7xctLW+K9q3PEWf+Sochw2nss8L98O3Sis68yRFy4IUPIPGunFrBbMFis48SdGyIAXPoLFu6nReOOFb3xWdeZKiZUEKnkFj3dTpvMhM+JLOlPS3kp6W9JSkG7psc4mkWUmPtX9u6k+4zVO0GFSFYlJWOwFYPs68feYHPcMmr+33bWd01yjaKUZ3jbL9vu3JYsyrCufFsKjTzKrRHNscBf4oIh6V9FbggKQHIuLHHds9FBGXpw+xuTqLQXOX+gMrKnb2+vspLddOIE+cWX3m57bbsX8Hh2YPsW7NOnZP7E5+CX3R19h+33b2TO+Zf34sjs0/X9gqop+qdF4MgzLOvVR6LtpK+i/ALRHxwIJllwB/3EvCd9E2WxnFzjKUcXPwusjT27/fhmk8m6i0oq2kDcD5wCNdVm+U9Likb0p6zxK/PylpWtL0zMxMz8E2TRnFzjKUcXPwusjT27/fhmk8rTe5E76ktwB/A3wiIl7pWP0osD4izgP+HPhGt31ExFREjEfE+NjY2Epjbowyip1lKOPm4HWRp7d/vw3TeFpvciV8SatpJfs7I+Jrnesj4pWIeLX9+H5gtaRTk0baQEWLQVUpJhVtJ1CV40ghT2//fhum8bTe5JmlI+CLwNMR8WdLbPOO9nZIuqi935dSBtpEW8/ZyjXnXbOo//o1512TuxhUlcv0t56zlY1rNy5atnHtxtztBKpyHCnk6e3fb8M0ntabzKKtpN8CHgKeBN5oL/4TYB1ARNwm6WPANlozen4F/NuI+G/L7ddF22zDcil/58yUOWUnOrNh4NYKQ2pYZlNUYWaK2bBwa4UhNSyzKaowM8XMnPArbVhmU1RhZoqZOeEvqQqXnueZTVGFOLNUYWZKldThPbPh5ITfxVyx9ODsQYKYv/S87P8xs2ZTVCXOLJvWbWJVx6m2ilVsWrdpQBENTl3eMxtOLtp2UZdiqeOsH4+FFeWibWJ1KZY6zvrxWNggOeF3UZdiqeOsH4+FDZITfhd1ufTccdaPx8IGyQm/i7pceu440yt6c5KsGTh1GgsbPi7amrUVbQExLK0wrNpctDVLYOrAVE/LO+3Yv2NRsgc48voRduzfUTg2sxSc8M3airaA8AwcqzonfLO2oi0gPAPHqs4J36ytaAsIz8CxqnPCN2srenMSz8CxqvMsHTOzGvEsHTMzy+SEb2bWEHluYn6mpL+V9LSkpyTd0GUbSfqcpGckPSHpgv6Ea53cW93M8hrNsc1R4I8i4lFJbwUOSHogIn68YJsPAO9q/7wP2NP+r/VR55Wdc73VARcKzew4mZ/wI+KFiHi0/fh/A08DZ3RsdiWwN1p+AJwi6bTk0doivrLTzHrR03f4kjYA5wOPdKw6A3huwfPDHP9HAUmTkqYlTc/MzPQWqR3HV3aaWS9yJ3xJbwH+BvhERLzSubrLrxw33zMipiJiPCLGx8bGeovUjuMrO82sF7kSvqTVtJL9nRHxtS6bHAbOXPB8LfB88fBsOb6y08x6kWeWjoAvAk9HxJ8tsdk+4Or2bJ2LgdmIeCFhnNaFr+w0s15kXmkr6beAh4AngTfai/8EWAcQEbe1/yjcAlwKHAGui4hlL6P1lbZmZr0rcqVt5rTMiPg+3b+jX7hNANevJAAzMyuHr7Q1M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGyHMT87+U9KKkHy2x/hJJs5Iea//clD5MMzMrKvOetsBf0bpB+d5ltnkoIi5PEpGZmfVF5if8iPge8HIJsZiZWR+l+g5/o6THJX1T0nsS7dPMzBLK85VOlkeB9RHxqqQPAt8A3tVtQ0mTwCTAunXrEry0mZnlVfgTfkS8EhGvth/fD6yWdOoS205FxHhEjI+NjRV9aTMz60HhhC/pHZLUfnxRe58vFd2vmZmllfmVjqQvA5cAp0o6DHwKWA0QEbcBVwHbJB0FfgVsiYjoW8RmZrYimQk/Iv4gY/0ttKZtmplZhflKWzOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhshM+JL+UtKLkn60xHpJ+pykZyQ9IemC9GGamVlReT7h/xVw6TLrPwC8q/0zCewpHpaZmaWWmfAj4nvAy8tsciWwN1p+AJwi6bRUAZqZWRqjCfZxBvDcgueH28te6NxQ0iStfwUAvLbU10QVcyrw80EHkYPjTKsOcdYhRnCcqf3GSn8xRcJXl2XRbcOImAKmACRNR8R4gtfvK8eZluNMpw4xguNMTdL0Sn83xSydw8CZC56vBZ5PsF8zM0soRcLfB1zdnq1zMTAbEcd9nWNmZoOV+ZWOpC8DlwCnSjoMfApYDRARtwH3Ax8EngGOANflfO2pFcQ7CI4zLceZTh1iBMeZ2orjVETXr9vNzGzI+EpbM7OGcMI3M2uIUhK+pBFJP5R0b5d1b5J0V7s1wyOSNpQRUzcZcV4raUbSY+2fjw4oxmclPdmO4bjpWVVpdZEjzkskzS4Yz5sGEOMpku6W9BNJT0va2LG+KmOZFWcVxvI3Frz+Y5JekfSJjm0GPp454xz4eLbj+DeSnpL0I0lflnRix/qec2eKefh53AA8Dbyty7qPAL+IiHdK2gJ8Bvj9kuLqtFycAHdFxMdKjGcpvxMRS10gsrDVxftotbp4X1mBdVguToCHIuLy0qI53n8EvhURV0k6ATipY31VxjIrThjwWEbE/wDeC60PTsDfA1/v2Gzg45kzThjweEo6A/g4cHZE/ErSV4EttFrdzOk5d/b9E76ktcBlwBeW2ORK4Pb247uBCUndLubqqxxx1oVbXeQg6W3AbwNfBIiI/xcRv+zYbOBjmTPOqpkA/mdEHOxYPvDx7LBUnFUxCrxZ0iitP/Kd1zf1nDvL+ErnZuCTwBtLrJ9vzRARR4FZ4O0lxNUpK06AD7X/KXq3pDOX2a6fAvi2pANqtarotFSri7JlxQmwUdLjkr4p6T1lBgf8M2AG+E/tr/G+IOnkjm2qMJZ54oTBjmWnLcCXuyyvwngutFScMODxjIi/B/4DcIhWm5rZiPh2x2Y9586+JnxJlwMvRsSB5TbrsqzUuaI547wH2BAR5wIP8o9/Wcu2KSIuoPXP4+sl/XbH+oGPZ1tWnI8C6yPiPODPgW+UHN8ocAGwJyLOB/4P8O86tqnCWOaJc9BjOa/9ldMVwH/utrrLsoHMC8+Ic+DjKemf0PoEfxZwOnCypA93btblV5cdz35/wt8EXCHpWeArwPsl3dGxzXxrhvY/XdawfHfOfsiMMyJeiojX2k8/D1xYbojzcTzf/u+LtL57vKhjk0q0usiKMyJeiYhX24/vB1ZLOrXEEA8DhyPikfbzu2kl1s5tBj2WmXFWYCwX+gDwaET8ry7rqjCec5aMsyLjuRn4WUTMRMTrwNeAf96xTc+5s68JPyJujIi1EbGB1j+fvhMRnX+l9gHXtB9f1d6m1L/6eeLs+K7xClrF3VJJOlnSW+ceA78LdHYcHXirizxxSnrH3PeNki6idS6+VFaMEfEPwHOS5joPTgA/7ths4GOZJ85Bj2WHP2Dpr0kGPp4LLBlnRcbzEHCxpJPasUxwfM7pOXeWNUtnEUm7gOmI2EerGPUlSc/Q+uu0ZRAxddMR58clXQEcpRXntQMI6deAr7fPxVHgryPiW5L+EAq3uig7zquAbZKOAr8CtpT9hx7418Cd7X/e/xS4roJjmSfOKowlkk4C/gXwrxYsq9x45ohz4OMZEY9IupvW10tHgR8CU0Vzp1srmJk1hK+0NTNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNriP8Pq8UAjgO63JUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(x, y, color='green')\n",
    "plt.xlim(4, 8)\n",
    "plt.ylim(1, 5)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "WkcMa9cs2onL"
   },
   "outputs": [],
   "source": [
    "# 定义聚类数的节点\n",
    "\n",
    "class ClusterNode:\n",
    "    def __init__(self, vec, left=None, right=None, distance=-1, id=None, count=1):\n",
    "        \"\"\"\n",
    "        :param vec: 保存两个数据聚类后形成新的中心\n",
    "        :param left: 左节点\n",
    "        :param right:  右节点\n",
    "        :param distance: 两个节点的距离\n",
    "        :param id: 用来标记哪些节点是计算过的\n",
    "        :param count: 这个节点的叶子节点个数\n",
    "        \"\"\"\n",
    "        self.vec = vec\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.distance = distance\n",
    "        self.id = id\n",
    "        self.count = count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "_M1vGW8s5ycx"
   },
   "outputs": [],
   "source": [
    "def euler_distance(point1: np.ndarray, point2: list) -> float:\n",
    "    \"\"\"\n",
    "    计算两点之间的欧拉距离，支持多维\n",
    "    \"\"\"\n",
    "    distance = 0.0\n",
    "    for a, b in zip(point1, point2):\n",
    "        distance += math.pow(a - b, 2)\n",
    "    return math.sqrt(distance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "udgrrhsn19X1"
   },
   "outputs": [],
   "source": [
    "# 层次聚类（聚合法）\n",
    "\n",
    "class Hierarchical:\n",
    "    def __init__(self, k):\n",
    "        self.k = k\n",
    "        self.labels = None\n",
    "        \n",
    "    def fit(self, x):\n",
    "        nodes = [ClusterNode(vec=v, id=i) for i, v in enumerate(x)]\n",
    "        distances = {}\n",
    "        point_num, feature_num = x.shape\n",
    "        self.labels = [-1] * point_num\n",
    "        currentclustid = -1\n",
    "        while(len(nodes)) > self.k:\n",
    "            min_dist = math.inf\n",
    "            nodes_len = len(nodes)\n",
    "            closest_part = None\n",
    "            for i in range(nodes_len - 1):\n",
    "                for j in range(i+1, nodes_len):\n",
    "                    d_key = (nodes[i].id, nodes[j].id)\n",
    "                    if d_key not in distances:\n",
    "                        distances[d_key] = euler_distance(nodes[i].vec, nodes[j].vec)\n",
    "                    d = distances[d_key]\n",
    "                    if d < min_dist:\n",
    "                        min_dist = d\n",
    "                        closest_part = (i, j)\n",
    "                        \n",
    "            part1, part2 = closest_part\n",
    "            node1, node2 = nodes[part1], nodes[part2]\n",
    "            new_vec = [ (node1.vec[i] * node1.count + node2.vec[i] * node2.count ) / (node1.count + node2.count)\n",
    "                        for i in range(feature_num)]\n",
    "            new_node = ClusterNode(vec=new_vec,\n",
    "                                   left=node1,\n",
    "                                   right=node2,\n",
    "                                   distance=min_dist,\n",
    "                                   id=currentclustid,\n",
    "                                   count=node1.count + node2.count)\n",
    "            currentclustid -= 1\n",
    "            del nodes[part2], nodes[part1]\n",
    "            nodes.append(new_node)\n",
    "            \n",
    "        self.nodes = nodes\n",
    "        self.calc_label()\n",
    "        \n",
    "    def calc_label(self):\n",
    "        \"\"\"\n",
    "        调取聚类的结果\n",
    "        \"\"\"\n",
    "        for i, node in enumerate(self.nodes):\n",
    "            # 将节点的所有叶子节点都分类\n",
    "            self.leaf_traversal(node, i)\n",
    "\n",
    "    def leaf_traversal(self, node: ClusterNode, label):\n",
    "        \"\"\"\n",
    "        递归遍历叶子节点\n",
    "        \"\"\"\n",
    "        if node.left == None and node.right == None:\n",
    "            self.labels[node.id] = label\n",
    "        if node.left:\n",
    "            self.leaf_traversal(node.left, label)\n",
    "        if node.right:\n",
    "            self.leaf_traversal(node.right, label)\n",
    "            \n",
    "# https://zhuanlan.zhihu.com/p/32438294"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 107
    },
    "colab_type": "code",
    "id": "LwD9Iots6871",
    "outputId": "be527c5e-3be7-40ee-c361-37a0ab57440b"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2\n",
      " 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 2 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
      " 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 1 0 0 1 2 1 0 1 0\n",
      " 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0\n",
      " 0 0]\n"
     ]
    }
   ],
   "source": [
    "my = Hierarchical(3)\n",
    "my.fit(data)\n",
    "labels = np.array(my.labels)\n",
    "print(labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 281
    },
    "colab_type": "code",
    "id": "yJN0NPWn8F6K",
    "outputId": "f8238840-dd5e-45b3-e5b2-b4fa3836f7bb"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEICAYAAABcVE8dAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3df5wkdX3n8dd7ZxZxACGRSRD2x8TThwYTVJhDyOaUZDeJ/AjkLiZusp5iJBtnNeqdOS9m74GwyZrkHl4kCceS8UeE7EYxRM2K6PkTEYzrLYggYu5BlFlWMYwgi7iGuMvn/qia3Z7enq7qqerq6qn38/Hox3RXVVd9qrrnMz31+danFRGYmdnSt2zQAZiZWTWc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCX+ISbpb0jk1iGNCUkgaXWD+H0h6Zz+30eV5F0u6pci2yzLo1yvrdej1WEm6T9K6cqKzKjjh11SnX6b2X8iIeE5E3FR5cD2KiLdGxCWDjqOI9I/NM4qsY9CvV+vrsNg/oGWTtF3SA5IelfT/JA31+6TunPAbaDG/5JJG+hFLEww6qdbcHwMTEfEU4ELgjySdMeCYliwn/CHW+l+ApGWSfl/SP0t6SNL7Jf1oOm/u09yrJO0BPp1O/ztJ35a0T9LNkp7Tsu73SNom6UZJ3wd+TtKTJf0vSTPpc26R9OSWkDZI2iPpO5I2t6zrMknbWx7/rKTPS3pE0v2SLk6nny/pS+mnvfslXdbDsVgp6QOSZtP9v7LDMkd8qpV009ynSknPkPTZdN++I+m6dPrN6eJflvSYpJem0y+QdEe6H5+XdFrba/PfJd0JfF/SaNvrdVn6Gl0r6Xvp6Z7Jluefnh6L76Wv03WS/miBfZ+ZS5KSXpbu46np40skfajD6zC3T4+k+3R2y/reJum7kr4h6dycx//Z6fLr8yw/JyLujojH5x6mt3/XyzosPyf8peN1wK8ALwJOBr4L/O+2ZV4E/CTwS+njjwLPBH4MuB3Y0bb8bwJbgeOAW4C3AWcAPwP8KPAm4ImW5X8WeBawFrhU0k+2BylpVbrdvwTGgecBd6Szvw+8HDgBOB+YkvQrWTue/vdxAzADTACnAO/Lel4Hfwh8HPgRYEUaIxHxwnT+cyPi2Ii4TtLpwLuB3wGeCvwVsFPSk1rW9xvpfpwQEQc6bO/CNM4TgJ3Alen+HAV8EHgPyXF+L/Afu8T9WeCc9P4Lga+TvNZzjz/b4Tlz+3RCuk//mD5+AfBPwInA/wTeJUldtk16LD4O/G5EvC+ddkP6h7DT7Ya2518laT/wNeAB4MZu27MCIsK3Gt6A+4DHgEdabvuBW9qWWZfevwdY2zLvacAPgVGSJBjA07ts74R0mePTx+8Brm2Zvwz4AUnSa3/u3PpXtEz7IrA+vX8ZsD29/2bggzmPwRXA29u2MdphubOB2QXmXTx3zDqtA7gJuCS9fy0w3bofLcsF8IyWx9uAP2xb5p+AF7W8Nr/V4TWde70uAz7ZMu9U4Afp/RcC3wTUMv8W4I8WOE6vAna2vA8uAd6XPp4BTu/wOnQ6FhcD97Y8HkuXOanLe/RyYC/wcwXf7yMkHxj+B7B8kL97S/nmT/j19isRccLcDdjUZdnVwAfnPkWR/OIfBH68ZZn75+5IGpH0J+kpoEdJfnkh+WR3xPLp9KOBf+4Sw7db7u8Hju2wzMqF1iHpBZI+k56W2Qe8ui2ehawEZqLzp+hevAkQ8MX0FMtvdVl2NfDG1k+uaRwntyxzf+enHtJ+vI5OTzedDHwz0kyYY12fBf6DpJNIEud1wBpJE8DxHP4PKo9DMUXE/vRup9dxzquBz0fEZ3rYxhEi4mBE3ELyn9VUkXXZwpzwl477gXNb/0BExNER8c2WZVoTyG8CFwHrSJLCRDpdCyz/HeBfKX5+9f4u6/hbklMbKyPieODqtni6rXOVsouj309/jrVMO2nuTkR8OyJ+OyJOJjlVc5UWHplzP7C17XiPRcR7W5ZZbCvaB4BT2k6lrFxo4Yi4l+QPxuuAmyPieySJeyPJfzdPdHraImNr92qSY//21omSPprWBjrdPtplfaP4HH7fOOEvHVcDWyWtBpA0LumiLssfBzwOPESSAN/abeVp0ng38GeSTk7/Qzi77Zx1HjuAdZJ+PS1kPlXS81piejgi/lXSmSR/lPL4IkmS/BNJx0g6WtKaDvswS3Kq5GVp/L9FS3KR9GuSVqQPv0uSFA+mj/8FeHrL6t4BvDr9r0Tpds+XdFzOmLv5x3S7r02P0UXAmRnP+SzwWg6fr7+p7XG7WZL6y9MXmJ/X94AXAy+U9CdzEyPi3EhqA51u5wJI+jFJ6yUdm74ev0RS9/h0wZhsAU74S8efk3w6/rik7wFfICnALeRakvO73wS+mi6f5feAu4D/CzwM/Ck9vociYg9wHvDGdB13AM9NZ28CtqTxXwq8P+c6DwK/DDwD2ENyTvmlCyz+28B/I/lD9xzg8y3z/j2wS9JjJMfy9RHxjXTeZcA16embX4+I3em6riT543AvyTnwwiLi34D/RHJu/hHgZSRF6ce7PO2zJH8wb17gcfs29pMU5G9N9+msAvE+AvwCcK6kP+zlqSSnb/aSHMO3AW+IiH9YbCzWneafJjSzOpK0C7g6Iv560LHY8PInfLMakvQiSSelp3ReAZwGfGzQcdlwy3UFoKT7SM7VHQQORMRk23yRnFI4j6R4dHFE3F5uqGaN8iySU1rHkoxqeklEPDDYkGzY5Tqlkyb8yYj4zgLzzwN+lyThvwD484jodv7YzMwqVtYpnYtILtKJiPgCcIKkp5W0bjMzK0Hepk5BMvojgL+KiOm2+acw/8KQvem0ef+CStpIMjaYY4455oxnP/vZiwrazKypbrvttu9ExPhinps34a+JiG9J+jHgE5K+FhGtw706XRxzxLmi9A/FNMDk5GTs3r2754DNzJpM0sxin5vrlE5EfCv9+SBJU6f2i0D2Mv9KwBXAtxYblJmZlS8z4adXEB43dx/4ReArbYvtBF6eXnF4FrDPIwrMzOolzymdHydpyjW3/N9GxMckvRogIq4maWd6HsnVhvuBV/YnXDMzW6zMhB8RX+fwpe+t069uuR/Aa8oNzczMyuQrbc3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCFyJ3xJI5K+JOmGDvMuljQr6Y70dkm5YZqZWVF5vsR8zuuBe4CnLDD/uoh4bfGQzMysH3J9wpe0AjgfeGd/wzEzs37Je0rnCuBNwBNdlvlVSXdKul7SyuKhmZlZmTITvqQLgAcj4rYui30YmIiI04BPAtcssK6NknZL2j07O7uogM3MbHHyfMJfA1wo6T7gfcDPS9reukBEPBQRj6cP3wGc0WlFETEdEZMRMTk+Pl4gbDMz61Vmwo+IN0fEioiYANYDn46Il7UuI+lpLQ8vJCnumpVmxw6YmIBly5KfO3YMOiKz4dPLKJ15JG0BdkfETuB1ki4EDgAPAxeXE55Zktw3boT9+5PHMzPJY4ANGwYXl9mwUUQMZMOTk5Oxe/fugWzbhsvERJLk261eDffdV3U0ZoMl6baImFzMc32lrdXenj29TTezzpzwrfZWreptupl15oRvtbd1K4yNzZ82NpZMN7P8nPCt9jZsgOnp5Jy9lPycnnbB1qxXix6lY1alDRuc4M2K8id8M7OGcMI3M2sIJ3wzs4ZwwrdKuDWC2eC5aGt959YIZvXgT/jWd5s3H072c/bvT6abWXWc8K3v3BrBrB6c8K3v3BrBrB6c8K3vBVW3RjCrByf8hpsrqM7MQMThgmqZSd+tEczqwf3wG8695s2Gi/vh26K5oGrWHE74DeeCqllzOOE3nAuqZs2RO+FLGpH0JUk3dJj3JEnXSbpX0i5JE2UGaf2zlAqqbt9g1l0vrRVeD9wDPKXDvFcB342IZ0haD/wp8NIS4rMKLIVe827fYJYt1yd8SSuA84F3LrDIRcA16f3rgbWSVDw8s3zcvsEsW95TOlcAbwKeWGD+KcD9ABFxANgHPLV9IUkbJe2WtHt2dnYR4Zp15tFGZtkyE76kC4AHI+K2bot1mHbEAP+ImI6IyYiYHB8f7yFMs+482sgsW55P+GuACyXdB7wP+HlJ29uW2QusBJA0ChwPPFxinFZjmzbB6GhS9B0dTR5XzaONzLJlJvyIeHNErIiICWA98OmIeFnbYjuBV6T3X5IuM5hLeK1SmzbBtm1w8GDy+ODB5HHVSX8pjTYy65eeWitIOgf4vYi4QNIWYHdE7JR0NPA3wPNJPtmvj4ivd1uXWyssDaOjh5N9q5EROHCg+njMlroirRV6+sariLgJuCm9f2nL9H8Ffm0xAdhw65Tsu003s8HxlbZWyMhIb9PNbHCc8K2QuYub8k43s8Fxwl/i1q1Liphzt3Xryl3/VVfB1NThT/QjI8njq64qdztum2C1VsYbtIo3eUQM5HbGGWeE9dfatRHJ15rMv61dO+jIerN9e8TY2Px9GBtLppsNXBlv0B7WQTJYZlF511+AsoR1a24xTINm/SUtVmtlvEF7WIe/AMWWNLdNsFor4w1a0ZvcCd9qz20TrNbKeINW9CZ3wl/C1q7tbfpCsmpJ/a41uW2C1VoZb9Cq3uSLPflf9Oaibf9t3x4hza8DSeXWkqoqqG7fHrF6dRL/6tUu2FrNlPEGzbkOXLS1TqqoJbmgalYtF22toypqSS6omg0PJ/wlrIpakguqZsPDCX+Rqrrys0jBtIpakguq1le+xLpciz35X/Q2zEXbKguVRQumVdSSXFC1vvAl1h3hom21qipUumBqjeY3eEdFirZO+IuwbFnn1gQSPLHQ17z3YTtVxWE2EH6Dd+RROhWrqlDpgqk1mt/gpXPCX4SqCpUumFqj+Q1evqyT/MDRwBeBLwN3A5d3WOZiYBa4I71dkrXeYS7aRlRXqMzaTnsL5PbWx1NTESMjybyRkeTxIPbFhV1bFL9xjkCBom2ehC/g2PT+cmAXcFbbMhcDV/ay4WFP+HUwNTU/2c/d5pJ61vyIagZCeLCFWXmKJPyeiraSxoBbgKmI2NUy/WJgMiJem3ddw1y0rYvR0c5fFj4yAgcOZM+HagZCeLCFWXn6XrSVNCLpDuBB4BOtyb7Fr0q6U9L1klYusJ6NknZL2j07O7uYeK1Fp2TeOj1rPlTTGsHtF8zqIVfCj4iDEfE8YAVwpqSfalvkw8BERJwGfBK4ZoH1TEfEZERMjo+PF4nbOPw9sgtNz5oP1QyE8GALs3roaZRORDwC3AS8uG36QxHxePrwHcAZpURXY2Vc8b1pU3LaRUp+btrU2/M3buw+PWs+JAMeli+fP3/58t4GQmTtxzANtthx1w4mrphg2eXLmLhigh139fbC5nl+0W2YLVZmwpc0LumE9P6TgXXA19qWeVrLwwuBe8oMsm527EiS5sxMUoKcmUke95L0N22Cbdvmn37Ztq33pN/NmjVJAm41OppMb9X+3bfdvgu3XZ792LABpqeTc/ZS8nN6OpleJzvu2sHGD29kZt8MQTCzb4aNH96YOyHneX7RbZgVkVm0lXQaySmaEZI/EO+PiC2StpBUi3dK+mOSRH8AeJikqPu1BVfKcBdtyyhC5imoFl1HnjiL7ksZ+1EXE1dMMLPvyIOx+vjV3PeG+0p5ftFtmLm1QsXKuOK726fovC9J1jryxFl0X8rYj7pYdvkygiODFuKJt2QfjDzPL7oNM7dWqFgZRcg8BdWi68gTZ9F9KWM/6mLV8Z13eqHpi3l+0W2YFeGEvwhlFCHzFFSLriNPnEX3pYz9qIuta7cytnz+wRhbPsbWtfkORp7nF92GWSGLvWKr6G3Yr7Qt44rvPG0PstShtUIZ+1EX2+/cHqvfvjp0mWL121fH9jt7Oxh5nr/2mrXBZRy6rb1mbYc19dfUDVMxcvlIcBkxcvlITN0wxC9aw+B++M00N1po//7D08bGDo+AyZpv1dv0kU1s273tiOlTk1Ncdf5VjYnBFs9F24byF6QMn9EtoxyMI4c1jWiEA5dWM6ypDjHY4rlo21BZLQvc0qB+OiXabtOXagw2GE74Q8xfkDJ8RtR5+NJC05dqDDYYjU34RVsj5Hl+0dYJWbZuhaOOmj/tqKP8BSkLqUNLg41ndB6+1Dp900c2MbplFF0uRreMsukj8984RfcjTwx5tlN0fi5l9DCxwxZb7S16G+QonaL92fM8P08v+jL2Y/ny+etfvnx+HP7+iMT2O7fH2NaxeaNjxraO9TwKpwzdRshM3TA1L8a529wyZe1H1iidrO0UnZ+Lv0ihIzxKpzdFi5l5nl9FywEXZfMblpYGWQXVqvYjaztF5+cLYsJv8A5ctO1R0WJmnufn6UVflIuy+e3Z1/mgLDR9ULIKqlXtR9Z2is7PF4Tf4GVrZMIvWszM8/wqWg64KJvfsLQ0yCqoVrUfWdspOj9fEH6Dl62RCb9oMTPP86toOeCibH7D0tIgq6Ba1X5kbafo/HxB+A1eusWe/C96G3RrhSraCWQtkyeGMtZhiaJtE6qS1XqhjP3I094hazunXnnqvHWceuWppcfpN/iRcNG2WmW0LMizjrkvF2k3NQVX+Qr4JWnuC1L2//DwG2Ns+RjTvzzNhp8upx/GumvX8alvfOqI6Wt/Yi2ffPknK1uHLY5bK1SsjMEDdRnpY/VSxSgcXb7wlxjEW/LlgzLWYYvjUToVK2PwQF1G+li9DMtoIhtOTviLUMbggbqM9LF6GZbRRDac8nyJ+dGSvijpy5LulnR5h2WeJOk6SfdK2iVpoh/B5pXnauwiV2yXMXhg69YjE/fISO8jfepw5XkZl9D3u51Anm3k2U6edRSRZ3TLumvXoct16Lbu2nU97cfan1jbcdvt08tYR6asN3Ad3uB54qhLnFmyqrqAgGPT+8uBXcBZbctsAq5O768Hrstab79G6eS5GruMK7bLGOWT1Xph+/aIZcvmz1+27PC26nDleRmX0FfRTiBrG3m2k2cdZeg2uqV9dE2nUTZl7EeeY174i1yy3sB1eIPXME6qGqUjaQy4BZiKiF0t0/8PcFlE/KOkUeDbwHh0WXm/irZ5iqF1uGI7T0F2GPrdl1FkrKKdQJ4e8FnbqUMf+TzF0jL2o5IWDsPwBofaxdn3oq2kEUl3AA8Cn2hN9qlTgPsBIuIAsA94aof1bJS0W9Lu2dnZxcSbKU8xtA5XbOcpyA5Dv/syioxVtBPI0wM+azvD0ke+jP2opHg8DG/wPHHUJc4cciX8iDgYEc8DVgBnSvqptkU6few44tN9RExHxGRETI6Pj/cebQ55iqF1uGI7T0F2GPrdl1FkrKKdQJ4e8FnbGZY+8mXsRyXF42F4g+eJoy5x5tDTKJ2IeAS4CXhx26y9wEqA9JTO8cDDJcTXszwF1TpcsZ2nIJsVZx32o4xL6KtoJ5CnB3zWdvL2ke+nPMXSMvajkhYOw/AGzxNHXeLMI+skPzAOnJDefzLwOeCCtmVew/yi7fuz1tvP1gpltCyoQp4YsvalDleeV3Gpf1b/9jzyrCNrmTLaHmQtkzU/T7E0az/yHItKWlEUfYNX9QtQlziiz0VbSacB1wAjJP8RvD8itkjakm54p6Sjgb8Bnk/yyX59RHy923oHeaVtGa0RrDxZ7QSqaDdQRhx54qxiX6s6XgPX0F9kt1boUV2K/5ao5Ms0KogjT5xV7OuwfNlLYQ39RXZrhR4NUVG9ESr5Mo0K4sgTZxX72pj2DP5F7lkjE/4QFdUboZIv06ggjjxxVrGvjWnP4F/knjUy4Q9TUb0Jtq7dyvJly+dNW75s+bwv02gfSjiikSNGjBRtv5DnSz2Wtf3KLGPZvPnd9iPvvnbbRp79LGuETRntLPoq7y9yFW0PhqS1QiMT/oYNSV1n9WqQkp9LvM5Te5IWfHzrnluPuFjoYBzk1j23Hno8V6ic2TdDEMzsm2Hjhzf2lKQ2/PQGpn95mtXHr0aI1cevnlfovHXPrTzBE/Oe8wRPzIuj237k3ddu28izn1n7kUcZx7Pv8vwizxV2Z2aSpgczM8njMhNyFdsoSSOLtlYvw9IKoIwWEEX3tS4F7KFRRWF3qbVWMOunYWkFUEYLiKL7WpcC9tCoorA7RMVjJ3wbuGFpBVBGC4ii+1qXAvbQqKKwO0TFYyd8G3i9aevarRw1ctS8aUeNHNVzK4CF1t2LboXKMlpAFN3XSloeVLidvqtihMYQjQJxwm+4utSb2mtJrY+vOv8qpianDn3KHdEIU5NTXHX+4W9yf+vNb+243oWmd5JVqMyKI2+xtNu+rlm1puMonTWr1vS0jaKq2k7fVTFCY4hGgbho23B1uFixjAJhGV+qXUWhsi5XFdvwctHWFq0O9aa6FAiriKMuVxVbMznhN1wd6k11KRBWEUddriq2ZnLCb7g61JvKKBCeeuKpPU3vVxxFt7FkiqVWS074DVdVvanb6Jc8BcKsy/zvfs3dnHzsyfOmnXzsydz9mrtzx1hGHEW3sWSKpU0z6KFuObloa31XtD97GX3m67AftkRV3Jff/fCt1oqOPCmjZUEZPILGOnJrBbPDio48KaNlQRk8gsY6qsNQt5yc8K3vio48KaNlQRk8gsY6qsNQt5wyE76klZI+I+keSXdLen2HZc6RtE/SHent0v6E2zxFa0F1qCVltROA7sXQvH3mBz3CJq9NH9nE6JZRdLkY3TLKpo9sKi3GvGrf636Y1GGoW06jOZY5ALwxIm6XdBxwm6RPRMRX25b7XERcUH6IzdVeC5prewD5akFFn1+mbu0E2ouhcy0NgEPF0Kw+83PLbf7UZvbs28Oq41exde3WUoupZWxj00c2sW33tkOPD8bBQ49bW0X0U57jbT2Y+2XavDk5jbNqVZLsl0JrBUn/AFwZEZ9omXYO8Hu9JHwXbbMVrQXVoW0CVPPl4MMiT2//fltKx7OJKivaSpoAng/s6jD7bElflvRRSc9Z4PkbJe2WtHt2drbnYJumaC2oLrWkKr4cfFjk6e3fb0vpeFpvcid8SccCfw+8ISIebZt9O7A6Ip4L/CXwoU7riIjpiJiMiMnx8fHFxtwYRWtBdaklVfHl4MMiT2//fltKx9N6kyvhS1pOkux3RMQH2udHxKMR8Vh6/0ZguaQTS420gYrWgupSSyraTmAptRvI09u/35bS8bTe5BmlI+BdwD0R8WcLLHNSuhySzkzX+1CZgTbRhg3wilfASPrhb2QkeZy3FlSXNt0bfnoDZ684e960s1ecnbudwFJqN5Cnt3+/LaXjab3JLNpK+lngc8BdwBPp5D8AVgFExNWSXgtMkYzo+QHwXyPi893W66Jttoqv2O6b9pEpc6pOdGZLgVsrLFF1GWVTVB1GppgtFW6tsETVZZRNUXUYmWJmTvi1VpdRNkXVYWSKmTnhL6gWLQlyjLKpQ5xZ6jAypU7c1sAGxQm/g7li6cwMRBxuSVB1Ms0aZVOXOLOsWbWGZW1vtWUsY82qNQOKaHDm2hrM7JshiENtDZz0rQou2nYwLMXSoYnTl/If4mNhRbloW7JhKZYOTZy+lP8QHwsbJCf8DoalWDo0cfpS/kN8LGyQnPA7qEtLgixDE6cv5T/Ex8IGyQm/g7q0JMgyNHEO0aX8Rb+cJGsEzjAdC1t6XLQ1SxVtAdH+xSKQfHp3QrcyuWhrVoLp26Z7mt5u86c2z0v2APt/uJ/Nn9pcODazMjjhm6WKtoDwCByrOyd8s1TRFhAegWN154RvliraAsIjcKzunPDNUkW/nMQjcKzuPErHzGyIeJSOmZllcsI3M2uIPF9ivlLSZyTdI+luSa/vsIwk/YWkeyXdKen0/oRr7YahH76Z1cNojmUOAG+MiNslHQfcJukTEfHVlmXOBZ6Z3l4AbEt/Wh+1f8n5XD98qF97BTMbvMxP+BHxQETcnt7/HnAPcErbYhcB10biC8AJkp5WerQ2z+bNh5P9nP37k+lmZu16OocvaQJ4PrCrbdYpwP0tj/dy5B8FJG2UtFvS7tnZ2d4itSMMSz98M6uH3Alf0rHA3wNviIhH22d3eMoR4z0jYjoiJiNicnx8vLdI7QjD0g/fzOohV8KXtJwk2e+IiA90WGQvsLLl8QrgW8XDs26GpR++mdVDnlE6At4F3BMRf7bAYjuBl6ejdc4C9kXEAyXGaR0MSz98M6uHPKN01gD/GbhL0h3ptD8AVgFExNXAjcB5wL3AfuCV5YdqnWzY4ARvZvlkJvyIuIXO5+hblwngNWUFZWZm5fOVtmZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hB5vsT83ZIelPSVBeafI2mfpDvS26Xlh2lmZkXl+RLz9wBXAtd2WeZzEXFBKRGZmVlfZH7Cj4ibgYcriMXMzPqorHP4Z0v6sqSPSnpOSes0M7MS5Tmlk+V2YHVEPCbpPOBDwDM7LShpI7ARYNWqVSVs2szM8ir8CT8iHo2Ix9L7NwLLJZ24wLLTETEZEZPj4+NFN21mZj0onPAlnSRJ6f0z03U+VHS9ZmZWrsxTOpLeC5wDnChpL/AWYDlARFwNvASYknQA+AGwPiKibxGbmdmiZCb8iPiNjPlXkgzbNDOzGvOVtmZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDZGZ8CW9W9KDkr6ywHxJ+gtJ90q6U9Lp5YdpZmZF5fmE/x7gxV3mnws8M71tBLYVD8vMzMqWmfAj4mbg4S6LXARcG4kvACdIelpZAZqZWTlGS1jHKcD9LY/3ptMeaF9Q0kaS/wIAHl/oNFHNnAh8Z9BB5Mw+lGoAAATHSURBVOA4yzUMcQ5DjOA4y/asxT6xjISvDtOi04IRMQ1MA0jaHRGTJWy/rxxnuRxneYYhRnCcZZO0e7HPLWOUzl5gZcvjFcC3SlivmZmVqIyEvxN4eTpa5yxgX0QccTrHzMwGK/OUjqT3AucAJ0raC7wFWA4QEVcDNwLnAfcC+4FX5tz29CLiHQTHWS7HWZ5hiBEcZ9kWHaciOp5uNzOzJcZX2pqZNYQTvplZQ1SS8CWNSPqSpBs6zHuSpOvS1gy7JE1UEVMnGXFeLGlW0h3p7ZIBxXifpLvSGI4YnlWXVhc54jxH0r6W43npAGI8QdL1kr4m6R5JZ7fNr8uxzIqzDsfyWS3bv0PSo5Le0LbMwI9nzjgHfjzTOP6LpLslfUXSeyUd3Ta/59xZxjj8PF4P3AM8pcO8VwHfjYhnSFoP/Cnw0oriatctToDrIuK1FcazkJ+LiIUuEGltdfECklYXL6gqsDbd4gT4XERcUFk0R/pz4GMR8RJJRwFjbfPrciyz4oQBH8uI+CfgeZB8cAK+CXywbbGBH8+cccKAj6ekU4DXAadGxA8kvR9YT9LqZk7PubPvn/AlrQDOB965wCIXAdek968H1krqdDFXX+WIc1i41UUOkp4CvBB4F0BE/FtEPNK22MCPZc4462Yt8M8RMdM2feDHs81CcdbFKPBkSaMkf+Tbr2/qOXdWcUrnCuBNwBMLzD/UmiEiDgD7gKdWEFe7rDgBfjX9V/R6SSu7LNdPAXxc0m1KWlW0W6jVRdWy4gQ4W9KXJX1U0nOqDA54OjAL/HV6Gu+dko5pW6YOxzJPnDDYY9luPfDeDtPrcDxbLRQnDPh4RsQ3gbcBe0ja1OyLiI+3LdZz7uxrwpd0AfBgRNzWbbEO0yodK5ozzg8DExFxGvBJDv9lrdqaiDid5N/j10h6Ydv8gR/PVFactwOrI+K5wF8CH6o4vlHgdGBbRDwf+D7w+23L1OFY5olz0MfykPSU04XA33Wa3WHaQMaFZ8Q58OMp6UdIPsH/BHAycIykl7Uv1uGpXY9nvz/hrwEulHQf8D7g5yVtb1vmUGuG9F+X4+nenbMfMuOMiIci4vH04TuAM6oN8VAc30p/Pkhy7vHMtkVq0eoiK86IeDQiHkvv3wgsl3RihSHuBfZGxK708fUkibV9mUEfy8w4a3AsW50L3B4R/9JhXh2O55wF46zJ8VwHfCMiZiPih8AHgJ9pW6bn3NnXhB8Rb46IFRExQfLv06cjov2v1E7gFen9l6TLVPpXP0+cbecaLyQp7lZK0jGSjpu7D/wi0N5xdOCtLvLEKemkufONks4keS8+VFWMEfFt4H5Jc50H1wJfbVts4McyT5yDPpZtfoOFT5MM/Hi2WDDOmhzPPcBZksbSWNZyZM7pOXdWNUpnHklbgN0RsZOkGPU3ku4l+eu0fhAxddIW5+skXQgcIInz4gGE9OPAB9P34ijwtxHxMUmvhsKtLqqO8yXAlKQDwA+A9VX/oQd+F9iR/nv/deCVNTyWeeKsw7FE0hjwC8DvtEyr3fHMEefAj2dE7JJ0PcnppQPAl4DpornTrRXMzBrCV9qamTWEE76ZWUM44ZuZNYQTvplZQzjhm5k1hBO+mVlDOOGbmTXE/wedMVUnY8SBMwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# visualize result\n",
    "\n",
    "cat1 = data[np.where(labels==0)]\n",
    "cat2 = data[np.where(labels==1)]\n",
    "cat3 = data[np.where(labels==2)]\n",
    "\n",
    "plt.scatter(cat1[:,0], cat1[:,1], color='green')\n",
    "plt.scatter(cat2[:,0], cat2[:,1], color='red')\n",
    "plt.scatter(cat3[:,0], cat3[:,1], color='blue')\n",
    "plt.title('Hierarchical clustering with k=3')\n",
    "plt.xlim(4, 8)\n",
    "plt.ylim(1, 5)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 107
    },
    "colab_type": "code",
    "id": "7xilKyap8ghX",
    "outputId": "0a58379a-679a-4d0b-fe13-241585f60d81"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n",
      " 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 2 0 2 0 1 0 1 1 0 2 0 2 0 2 2 2 2 0 0 2 0\n",
      " 0 0 0 0 0 2 2 2 2 0 2 0 0 2 2 2 2 0 2 1 2 2 2 0 1 2 0 2 0 0 0 0 1 0 0 0 0\n",
      " 0 0 2 2 0 0 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0\n",
      " 0 0]\n"
     ]
    }
   ],
   "source": [
    "sk = cluster.AgglomerativeClustering(3)\n",
    "sk.fit(data)\n",
    "labels_ = sk.labels_\n",
    "print(labels_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 281
    },
    "colab_type": "code",
    "id": "hlFZeDdW9Bzr",
    "outputId": "7a837637-70e6-4c40-b6f2-c6a651fc4cae"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEICAYAAABcVE8dAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3df5wkdX3n8dd7fqw4gJDIJPzY3Vk9fWgwosIcQjanJLNJ5IeQu5i4yXoGI9k4q1HvkvNiuAcCyZofDy9iwu2S1Rghs1EMUYMEPUVFRCPegggSTB5EGVjBsIIs4hri7n7uj6phe3p6pqqnqqurp97Px6Mf211VXfWp6t5P99TnW59WRGBmZivfUL8DMDOzajjhm5k1hBO+mVlDOOGbmTWEE76ZWUM44ZuZNYQT/gCTdJekM2oQxzpJIWlkkfm/K+k9vdzGEs87X9LNRbZdln6/XlmvQ7fHStK9kjaUE51VwQm/pjr9Z2r/DxkRz4uIGysPrksR8faIuKDfcRSRftg8q8g6+v16tb4Oy/0ALZukGUkPSnpM0j9LGuj3Sd054TfQcv6TSxruRSxN0O+kWnN/AKyLiKcB5wK/L+mUPse0YjnhD7DWvwIkDUn6HUn/IulhSR+U9MPpvLlvc6+VdB/w6XT630j6lqS9km6S9LyWdb9P0nZJ10v6HvBTkp4q6X9Lmk2fc7Okp7aEtEnSfZK+LenClnVdLGmm5fFPSvqCpEcl3S/p/HT62ZK+nH7bu1/SxV0cizWSPiRpT7r/l3dYZsG3Wkk3zn2rlPQsSZ9N9+3bkq5Op9+ULv4VSY9LemU6/RxJt6f78QVJJ7W9Nv9T0h3A9ySNtL1eF6ev0VWSvpue7plsef7J6bH4bvo6XS3p9xfZ99m5JCnpVek+npg+vkDSRzq8DnP79Gi6T6e3rO8dkr4j6RuSzsx5/J+bLr8xz/JzIuKuiHhi7mF6+w/drMPyc8JfOd4I/DzwUuB44DvA/2lb5qXAjwE/lz7+GPBs4EeA24Cdbcv/CrAVOBK4GXgHcArwE8APA28BDrYs/5PAc4Ap4CJJP9YepKS16Xb/DBgHXgjcns7+HvBq4GjgbGBa0s9n7Xj618d1wCywDjgB+EDW8zr4PeATwA8Bq9MYiYiXpPNfEBFHRMTVkk4G3gv8BvB04M+BayU9pWV9v5zux9ERsb/D9s5N4zwauBa4PN2fVcCHgfeRHOf3A/95ibg/C5yR3n8J8HWS13ru8Wc7PGdun45O9+kf0scvBv4JOAb4Y+AvJGmJbZMei08AvxkRH0inXZd+EHa6Xdf2/G2S9gFfAx4Erl9qe1ZARPhWwxtwL/A48GjLbR9wc9syG9L7dwNTLfOOA34AjJAkwQCeucT2jk6XOSp9/D7gqpb5Q8D3SZJe+3Pn1r+6ZdqXgI3p/YuBmfT+W4EP5zwGlwHvbNvGSIflTgf2LDLv/Llj1mkdwI3ABen9q4AdrfvRslwAz2p5vB34vbZl/gl4actr82sdXtO51+ti4IaWeScC30/vvwT4JqCW+TcDv7/IcXotcG3L++AC4APp41ng5A6vQ6djcT5wT8vjsXSZY5d4j14C7AZ+quD7fZjkC8P/Akb7+X9vJd/8Db/efj4ijp67AVuWWHYC+PDctyiS//gHgB9tWeb+uTuShiX9YXoK6DGS/7yQfLNbsHw6/TDgX5aI4Vst9/cBR3RYZs1i65D0YkmfSU/L7AVe1xbPYtYAs9H5W3Q33gII+FJ6iuXXllh2Avit1m+uaRzHtyxzf+enPqn9eB2Wnm46HvhmpJkwx7o+C/wnSceSJM6rgfWS1gFHcegvqDyejCki9qV3O72Oc14HfCEiPtPFNhaIiAMRcTPJX1bTRdZli3PCXznuB85s/YCIiMMi4psty7QmkF8BzgM2kCSFdel0LbL8t4F/o/j51fuXWMdfk5zaWBMRRwFXtMWz1DrXKrs4+r3037GWacfO3YmIb0XEr0fE8SSnarZp8ZE59wNb2473WES8v2WZ5baifRA4oe1UyprFFo6Ie0g+MN4I3BQR3yVJ3JtJ/ro52Olpy4yt3etIjv07WydK+lhaG+h0+9gS6xvB5/B7xgl/5bgC2CppAkDSuKTzllj+SOAJ4GGSBPj2pVaeJo33An8i6fj0L4TT285Z57ET2CDpl9JC5tMlvbAlpkci4t8knUryoZTHl0iS5B9KOlzSYZLWd9iHPSSnSl6Vxv9rtCQXSb8oaXX68DskSfFA+vhfgWe2rO7dwOvSv0qUbvdsSUfmjHkp/5Bu9w3pMToPODXjOZ8F3sCh8/U3tj1ut4ek/vLMRebn9V3gZcBLJP3h3MSIODOS2kCn25kAkn5E0kZJR6Svx8+R1D0+XTAmW4QT/srxLpJvx5+Q9F3giyQFuMVcRXJ+95vAP6bLZ/lt4E7g/wGPAH9El++hiLgPOAv4rXQdtwMvSGdvAS5N478I+GDOdR4AXg48C7iP5JzyKxdZ/NeB/0HyQfc84Ast8/4jcIukx0mO5Zsi4hvpvIuBK9PTN78UEbvSdV1O8uFwD8k58MIi4t+B/0Jybv5R4FUkReknlnjaZ0k+MG9a5HH7NvaRFOQ/n+7TaQXifRT4GeBMSb/XzVNJTt/sJjmG7wDeHBF/t9xYbGmaf5rQzOpI0i3AFRHxl/2OxQaXv+Gb1ZCkl0o6Nj2l86vAScDH+x2XDbZcVwBKupfkXN0BYH9ETLbNF8kphbNIikfnR8Rt5YZq1ijPITmldQTJqKZXRMSD/Q3JBl2uUzppwp+MiG8vMv8s4DdJEv6LgXdFxFLnj83MrGJlndI5j+QinYiILwJHSzqupHWbmVkJ8jZ1CpLRHwH8eUTsaJt/AvMvDNmdTpv3J6ikzSRjgzn88MNPee5zn7usoM3MmurWW2/9dkSML+e5eRP++oh4QNKPAJ+U9LWIaB3u1enimAXnitIPih0Ak5OTsWvXrq4DNjNrMkmzy31urlM6EfFA+u9DJE2d2i8C2c38KwFXAw8sNygzMytfZsJPryA8cu4+8LPAV9sWuxZ4dXrF4WnAXo8oMDOrlzyndH6UpCnX3PJ/HREfl/Q6gIi4gqSd6VkkVxvuA17Tm3DNzGy5MhN+RHydQ5e+t06/ouV+AK8vNzQzMyuTr7Q1M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGyJ3wJQ1L+rKk6zrMO1/SHkm3p7cLyg3TzMyKyvMj5nPeBNwNPG2R+VdHxBuKh2RmZr2Q6xu+pNXA2cB7ehuOmZn1St5TOpcBbwEOLrHML0i6Q9I1ktYUD83MzMqUmfAlnQM8FBG3LrHYR4F1EXEScANw5SLr2ixpl6Rde/bsWVbAZma2PHm+4a8HzpV0L/AB4KclzbQuEBEPR8QT6cN3A6d0WlFE7IiIyYiYHB8fLxC2mZl1KzPhR8RbI2J1RKwDNgKfjohXtS4j6biWh+eSFHfNyrNzJ6xbB0NDyb87d/Y7IrOB080onXkkXQrsiohrgTdKOhfYDzwCnF9OeGYkyX3zZti3L3k8O5s8Bti0qX9xmQ0YRURfNjw5ORm7du3qy7ZtwKxblyT5dhMTcO+9VUdj1leSbo2IyeU811faWv3dd193082sIyd8q7+1a7ubbmYdOeFb/W3dCmNj86eNjSXTzSw3J3yrv02bYMeO5Jy9lPy7Y4cLtmZdWvYoHbNKbdrkBG9WkL/hm5k1hBO+mVlDOOGbmTWEE75Vw60RzPrORVvrPbdGMKsFf8O33rvwwkPJfs6+fcl0M6uME771nlsjmNWCE771nlsjmNWCE771vqDq1ghmteCE33RzBdXZWYg4VFAtM+m7NYJZLbgfftO517zZQHE/fFs+F1TNGsMJv+lcUDVrDCf8pnNB1awxcid8ScOSvizpug7zniLpakn3SLpF0royg7QeWkkFVbdvMFtSN60V3gTcDTytw7zXAt+JiGdJ2gj8EfDKEuKzKqyEXvNu32CWKdc3fEmrgbOB9yyyyHnAlen9a4ApSSoenllObt9glinvKZ3LgLcABxeZfwJwP0BE7Af2Ak9vX0jSZkm7JO3as2fPMsI1W4RHG5llykz4ks4BHoqIW5darMO0BQP8I2JHRExGxOT4+HgXYZpl8Ggjs0x5vuGvB86VdC/wAeCnJc20LbMbWAMgaQQ4CnikxDitzrZsgZGRpOg7MpI8rppHG5llykz4EfHWiFgdEeuAjcCnI+JVbYtdC/xqev8V6TL9uYTXqrVlC2zfDgcOJI8PHEgeV530V9JoI7Me6aq1gqQzgN+OiHMkXQrsiohrJR0G/BXwIpJv9hsj4utLrcutFVaIkZFDyb7V8DDs3199PGYrXJHWCl394lVE3AjcmN6/qGX6vwG/uJwAbMB1SvZLTTezvvGVtlbM8HB3082sb5zwrZi5i5vyTjezvnHCX+k2bEiKmHO3DRvKXf+2bTA9fegb/fBw8njbtnK347YJVmM779zJusvWMXTJEOsuW8fOO7t/f5axjizuh7+SbdgAn/rUwulTU3DDDdXHs1ztbRMgGXLpUThWAzvv3Mnmj25m3w8OvT/HRsfY8fIdbHp+vvdnN+soUrR1wl/JlupuMUijZv0jLVZj6y5bx+zehe/PiaMmuPfN95a+Dv8Aiq1sbptgNXbf3s7vw8Wm92odeTjhW/25bYLV2NqjOr8PF5veq3Xk4YS/kk1NdTd9MVkF014XVN02wWps69RWxkbnvz/HRsfYOpX//VnGOnKJiL7cTjnllLAem5mJkCKSM/bJTUqmd7OOsbH56xgbO7SOrPll7svERBL/xET56zcrYOaOmZh450ToYsXEOydi5o7u359510HS4WBZeddF25WsjGJn1jpcUDWrlIu21lkZxc6sdbigajYwnPBXsjKKnVnrcEHVbGA44S9XVVd+FimYllHszFqHC6rWQ1Vcfdooyz35X/Q20EXbKguVRQumZRQ7s9bhgqr1wMwdMzG2dSy4mCdvY1vHllUQXUlw0bZiVRUqXTC1BivjCtaVyEXbqlVVqHTB1BqsqqtPm8QJfzmqKlS6YGoNVtXVp03ihL8cVRUqXTC1Bqvs6tMGyUz4kg6T9CVJX5F0l6RLOixzvqQ9km5Pbxf0JtyaqOoHs7O2s2kTnH76/Oecfvr8OLZsSX53Vkr+7fTj4lWMOHI/e+vSpudvYsfLdzBx1ARCTBw10VXLYesgq6oLCDgivT8K3AKc1rbM+cDl3VSLB3qUTl1MT88foTN3m57ONz+imhFHVY1qMmsAqhqlI2kMuBmYjohbWqafD0xGxBvyrmugR+nUxchI5x8LHx6G/fuz50M1I308msisND0fpSNpWNLtwEPAJ1uTfYtfkHSHpGskrVlkPZsl7ZK0a8+ePcuJ11p1Suat07PmQzUjfTyayKwWciX8iDgQES8EVgOnSvrxtkU+CqyLiJOAG4ArF1nPjoiYjIjJ8fHxInEbHPod2cWmZ82Hakb6eDSRWS10NUonIh4FbgRe1jb94Yh4In34buCUUqKrszKKkHkKqkvZvHnp6VnzIRnRMzo6f/7oaHcjfbL2Y4BGExW9lD/P890uwPolzyidcUlHp/efCmwAvta2zHEtD88F7i4zyNqZ+1Ht2dmkBDk7mzzuJulv2QLbt88//bJ9e/dJfynr1ycJuNXISDK9Vftv3y71W7jt8uxHVaOaCpr7IenZvbMEwezeWTZ/dHPuhJzn+UW3YVZEZtFW0kkkp2iGST4gPhgRl0q6lKRafK2kPyBJ9PuBR0iKul9bdKUMeNG2jCJknoJq0XXkibPovpSxHzVR9FL+PM93uwArqkjR1r10lmNoKPlm306CgwfzrWOpb9F5X5OsdeSJs+i+lLEfNTF0yRDBwpiFOPi27GOR5/lFt2HmXjpVK6MImaegWnQdeeIsui9l7EdNFL2UP8/z3S7A+skJfznKKELmKagWXUeeOIvuSxn7URNFL+XP83y3C7C+Wu4VW0VvA3+lbRk94KenI4aHkytPh4fnXwGb19TU/CtYp6a630bRfSljP2qi6I9R53n+1JVT83q8T1051WFNvTV93XQMXzIcXEwMXzIc09cN7mvWNLgffkPNjRbat+/QtLGxQyNgsuZb5bb8/Ra279q+YPr05DTbzt7WmBhs+Vy0bSr/QMrAGbl0hAOxcFTTsIbZf1E1o5rqEIMtn4u2TeUfSBk4nRLtUtNXagzWH074g8w/kDJwhtV59NJi01dqDNYfzU34RVsj5Hl+0dYJWbZuhVWr5k9btco/kLKIOrQ02HxK59FLrdO3/P0WRi4dQZeIkUtH2PL38983RfcjTwx5tlN0fh51eM1WlOVWe4ve+jpKp2h/9jzPz9OLvoz9GB2dv/7R0flxlDGaaAWYuWMmxraOzRsdM7Z1rOtROGVYaoTM9HXT82Kcu80tU9Z+ZI3SydpO0fl51Ok1qxM8SqdLRYuZeZ5fRcsBF2VzG5SWBlkF1ar2I2s7ReeXEUNTuWjbraLFzDzPz9OLvigXZXO7b2/nY7LY9H7JKqhWtR9Z2yk6v4wYrHvNTPhFi5l5nl9FywEXZXMblJYGWQXVqvYjaztF55cRg3WvmQm/aDEzz/OraDngomxug9LSIKugWtV+ZG2n6PwyYrBlWO7J/6K3vrdWqKKdQNYyeWIoYx0WEcXbJlQlq/VCGfuRp71D1nZOvPzEees48fITS49zUF6zKuGibcXKaFmQZx1zPy7SbnoatvkS+JVo7gdS9v3g0PtibHSMHS/fwabnl9MOY8NVG/jUNz61YPrUM6a44dU3VLYOWx63VqhaGaNj6jLSx2qlipEpumTx3zCIt+XLB2Wsw5bHo3SqVsbomLqM9LFa8cgU6yUn/OUoY3RMXUb6WK14ZIr1Up4fMT9M0pckfUXSXZIu6bDMUyRdLekeSbdIWteLYHPL0/agSGuFMkbHbN26MHEPD3c/0qdoi4gSlBFCVheKUraR0bIAsi/lz7OOIvKMTNlw1QZ0iZ68bbhqQ1f7MfWMqY7bbp9exjqyVNGeoQyDEmemrKouIOCI9P4ocAtwWtsyW4Ar0vsbgauz1tuzUTp52h4Uba0wt46io3yyWi/MzEQMDc2fPzR0aFtl7EdBZYSQdShK2UZGy4KI7Ev586yjDEuNTGkfXdNplE0Z+5GnrUHRH3Kpoj1DGeoWJ1WN0pE0BtwMTEfELS3T/y9wcUT8g6QR4FvAeCyx8p4VbfMUQ+vQkiBPQXYA+t2XEULWoShlGzl6wGcVTOvQRz5PsbSM/aiieFxFe4Yy1C3OnhdtJQ1Luh14CPhka7JPnQDcDxAR+4G9wNM7rGezpF2Sdu3Zs2c58WbLUwytQ0uCPAXZAeh3X0YIWYeilG3k6AGfVTAdlD7yZexHFcXjKtozlGFQ4swjV8KPiAMR8UJgNXCqpB9vW6TT144F3+4jYkdETEbE5Pj4ePfR5pGnGFqHlgR5CrID0O++jBCyDkUp28jRAz6rYDoofeTL2I8qisdVtGcow6DEmUdXo3Qi4lHgRuBlbbN2A2sA0lM6RwGPlBBf9/IUVOvQkiBPQTYrzhrsRxkhZB2KUraRowd8VsE0bx/5XspTLC1jP6poa1BFe4YyDEqcuWSd5AfGgaPT+08FPgec07bM65lftP1g1np72lqhjJYFVcgTQ9a+1KC1QhkhTE3NL8pOtdX/yni5snrA51mmjLYHWctkzc9TLM3ajzzHooq2BkWPRVWtF+oSR0SPi7aSTgKuBIZJ/iL4YERcKunSdMPXSjoM+CvgRSTf7DdGxNeXWm9fr7QtozWClSbr5ajq5cpqa1B0fhnbKGM/Voqm7Gc7t1boVg1Gt9ghdRmMVMWPfviHQ8rTlP1s59YK3arB6BY7pC6Dkar40Q//cEh5mrKfZWpmwq/B6BY7pC6Dkar40Q//cEh5mrKfZWpmwq/B6BY7ZOtWGB2dP210dP5gpKwuFFC8/UKe0RhDbf9lhhiaN390aP6OjA6NzhutkbVM1jYg+zL+skaN1L1dQN79rGI/6n6s5jQz4W/alFT8JiaS5i0TEy7Y9pm0+OPPf37hxVkHDiTT58wVdmdnk3E+s7PJ426S/qbnb2LHy3cwcdQEQkwcNTGvAPj5+z7PQQ7Oe85BDvL5+w4ForYdaX+ctUzWNuYKlbN7ZwmC2b2zbP7o5nkJJms/8siznX7Ls59V7McgHKs5zSzaWq1kFWXL6EJRhqyWBGUUbcvYRhlWSkG0Di0iyuairQ20rKJsGV0oypDVkqCMom0Z2yjDSimI1qFFRJ044VvfZRVly+hCUYaslgRlFG3L2EYZVkpBtA4tIurECd/63lN/61ZYtWr+tFWrDhVl83ahWGzd3Viq+JbVkiBPEXHr1FZWDc/f2VXDq3K3PajqMv6BahewhDq0iKgTJ/ymK6PaWYL2UlLr423bkt9tn/tGPzy88Hfc3/72zutdbHonWcW3bWdvY3py+slv28MaZnpymm1nJ4HkLZa2181aH69fu77jKJ31a9d3tY2iqtpOr1WxH4N0rFy0bboaXHVcRggdBsM8Ke9bvA4FvpVSLLXecdHWlq8GVx3XIIRkezUo8A1SAdAGjxN+09XgquMahJBsrwYFvkEqANrgccJvuhpcdVxGCCee2N30jnHUoMA3SAVAG0DL7atc9NbTfvjWnQp66hdt658nxOOPn99T//jjlxFnBX3P69Rb3cqxYvrh94qLts1RtJ99nudX0TO/qf3XbWlVvy/cD99qregonDzPr2KwkUfQWCdurWDWougonDzPr2Kkj0fQWCeD9L5wwreeKzoKJ8/zqxjp4xE01skgvS8yE76kNZI+I+luSXdJelOHZc6QtFfS7entot6E20BF2x70uW0CZLdOgKXDzOqXP7dMrwcblTWCZsuWpAOolPy7ZUt5MeY1KP3bB8FAjazKquoCxwEnp/ePBP4ZOLFtmTOA67qpFnuUTg4zMxFjY/OHnoyN5R9FU/T5JZmZiRgdnR/G6OihMLLCnJmJWLVq/vxVq5Y3kqfwvhQcjTE9PX8/5m7T0+XHupiZO2ZibOtYcDFP3sa2jnk0UAErdpSOpL8DLo+IT7ZMOwP47Yg4J+96XLTNoYpqZwWK/kh5TXajFHl6+/eai8+DrbJROpLWATcBPx4Rj7VMPwP4W2A38ABJ8r+rw/M3A5sB1q5de8psp//FdsjQUOdGMBIcPLhwetnPL0lWGEXnD5Iyev4UNXTJEMHCjQlx8G0DdkAbqJJROpKOIEnqb25N9qnbgImIeAHwZ8BHOq0jInZExGRETI6Pjy8n3mapotpZgaI/Ul6T3ShFnt7+vTZIRUYrV66EL2mUJNnvjIgPtc+PiMci4vH0/vXAqKRjSo20iYpWImvQNiFPGEXnD5I8vf17baCKjFaurJP8gICrgMuWWOZYDp0eOhW4b+7xYjcXbXOano4YHk4qe8PD3Vf3qqhk5jA1Nb9IOTU1f34ZrRUGRdGXtAxu3zC46GXRVtJPAp8D7gTmTvD9LrA2/cC4QtIbgGlgP/B94L9HxBeWWq+LtjlU0S+gAlu2wPbtC6e3/4iJmWVza4WVaoUMT6nDyBSzlcKtFVaquvwySEGdkv1S082sN5zw62yFDE+pw8gUM3PCX1wNWhLkGp5Shzgz1GFkSp0MwEtmK9Vyq71Fb7UepVOTlgRPxrLY8JQ6xbmEmZmIoaH5YQ4N1S7MSgzIS2Y1hn8ApWSDUiwdkDgHJMxK+FhYUR6lU7ZBuZZ/QOIckDAr4WNhRXmUTtkGpVg6IHEOSJiV8LGwfnLC72RQruUfkDgHJMxK+FhYXy335H/RW62LthGDcy3/gMQ5IGFW0sliUI6F1RMu2poVV7QFxArphGE156KtWQmKtoDwCByrgou2ZiUo2gJihXTCsBXMCd8sVbQFhEfgWN054ZuliraA8AgcqzsnfLPUtm1JgXbuG/3wcHc9+zdtSgq0ExPJhVQTEy7YWr24aGtmNkBctDUzs0xO+GZmDZGZ8CWtkfQZSXdLukvSmzosI0l/KukeSXdIOrk34doCbq5uZjmN5FhmP/BbEXGbpCOBWyV9MiL+sWWZM4Fnp7cXA9vTf62X2i/tnJ09NKTElUIza5P5DT8iHoyI29L73wXuBk5oW+w84Kq01cMXgaMlHVd6tDbfhRfOv44fkscXXtifeMys1ro6hy9pHfAi4Ja2WScA97c83s3CDwUkbZa0S9KuPXv2dBepLeRLO82sC7kTvqQjgL8F3hwRj7XP7vCUBeM9I2JHRExGxOT4+Hh3kdpCvrTTzLqQK+FLGiVJ9jsj4kMdFtkNrGl5vBp4oHh4tiRf2mlmXcgzSkfAXwB3R8SfLLLYtcCr09E6pwF7I+LBEuO0Tnxpp5l1Ic8onfXAfwXulHR7Ou13gbUAEXEFcD1wFnAPsA94TfmhWkebNjnBm1kumQk/Im6m8zn61mUCeH1ZQZmZWfl8pa2ZWUM44ZuZNYQTvplZQzjhm5k1hBO+mVlDOOGbmTWEE76ZWUM44ZuZNYQTvplZQzjhm5k1hBO+mVlDOOGbmTWEE76ZWUM44ZuZNYQTvplZQzjhm5k1hBO+mVlDOOGbmTVEnh8xf6+khyR9dZH5Z0jaK+n29HZR+WGamVlReX7E/H3A5cBVSyzzuYg4p5SIzMysJzK/4UfETcAjFcRiZmY9VNY5/NMlfUXSxyQ9r6R1mplZifKc0slyGzAREY9LOgv4CPDsTgtK2gxsBli7dm0JmzYzs7wKf8OPiMci4vH0/vXAqKRjFll2R0RMRsTk+Ph40U2bmVkXCid8ScdKUnr/1HSdDxddr5mZlSvzlI6k9wNnAMdI2g28DRgFiIgrgFcA05L2A98HNkZE9CxiMzNblsyEHxG/nDH/cpJhm2ZmVmO+0tbMrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCGc8M3MGsIJ38ysIZzwzcwawgnfzHxbp4oAAAVHSURBVKwhnPDNzBrCCd/MrCEyE76k90p6SNJXF5kvSX8q6R5Jd0g6ufwwzcysqDzf8N8HvGyJ+WcCz05vm4HtxcMyM7OyZSb8iLgJeGSJRc4DrorEF4GjJR1XVoBmZlaOkRLWcQJwf8vj3em0B9sXlLSZ5K8AgCcWO01UM8cA3+53EDk4znINQpyDECM4zrI9Z7lPLCPhq8O06LRgROwAdgBI2hURkyVsv6ccZ7kcZ3kGIUZwnGWTtGu5zy1jlM5uYE3L49XAAyWs18zMSlRGwr8WeHU6Wuc0YG9ELDidY2Zm/ZV5SkfS+4EzgGMk7QbeBowCRMQVwPXAWcA9wD7gNTm3vWMZ8faD4yyX4yzPIMQIjrNsy45TER1Pt5uZ2QrjK23NzBrCCd/MrCEqSfiShiV9WdJ1HeY9RdLVaWuGWyStqyKmTjLiPF/SHkm3p7cL+hTjvZLuTGNYMDyrLq0ucsR5hqS9Lcfzoj7EeLSkayR9TdLdkk5vm1+XY5kVZx2O5XNatn+7pMckvbltmb4fz5xx9v14pnH8N0l3SfqqpPdLOqxtfte5s4xx+Hm8CbgbeFqHea8FvhMRz5K0Efgj4JUVxdVuqTgBro6IN1QYz2J+KiIWu0CktdXFi0laXby4qsDaLBUnwOci4pzKolnoXcDHI+IVklYBY23z63Iss+KEPh/LiPgn4IWQfHECvgl8uG2xvh/PnHFCn4+npBOANwInRsT3JX0Q2EjS6mZO17mz59/wJa0Gzgbes8gi5wFXpvevAaYkdbqYq6dyxDko3OoiB0lPA14C/AVARPx7RDzatljfj2XOOOtmCviXiJhtm97349lmsTjrYgR4qqQRkg/59uubus6dVZzSuQx4C3BwkflPtmaIiP3AXuDpFcTVLitOgF9I/xS9RtKaJZbrpQA+IelWJa0q2i3W6qJqWXECnC7pK5I+Jul5VQYHPBPYA/xlehrvPZIOb1umDscyT5zQ32PZbiPw/g7T63A8Wy0WJ/T5eEbEN4F3APeRtKnZGxGfaFus69zZ04Qv6RzgoYi4danFOkyrdKxozjg/CqyLiJOAGzj0yVq19RFxMsmfx6+X9JK2+X0/nqmsOG8DJiLiBcCfAR+pOL4R4GRge0S8CPge8Dtty9ThWOaJs9/H8knpKadzgb/pNLvDtL6MC8+Is+/HU9IPkXyDfwZwPHC4pFe1L9bhqUsez15/w18PnCvpXuADwE9Lmmlb5snWDOmfLkexdHfOXsiMMyIejogn0ofvBk6pNsQn43gg/fchknOPp7YtUotWF1lxRsRjEfF4ev96YFTSMRWGuBvYHRG3pI+vIUms7cv0+1hmxlmDY9nqTOC2iPjXDvPqcDznLBpnTY7nBuAbEbEnIn4AfAj4ibZlus6dPU34EfHWiFgdEetI/nz6dES0f0pdC/xqev8V6TKVfurnibPtXOO5JMXdSkk6XNKRc/eBnwXaO472vdVFnjglHTt3vlHSqSTvxYerijEivgXcL2mu8+AU8I9ti/X9WOaJs9/Hss0vs/hpkr4fzxaLxlmT43kfcJqksTSWKRbmnK5zZ1WjdOaRdCmwKyKuJSlG/ZWke0g+nTb2I6ZO2uJ8o6Rzgf0kcZ7fh5B+FPhw+l4cAf46Ij4u6XVQuNVF1XG+ApiWtB/4PrCx6g964DeBnemf918HXlPDY5knzjocSySNAT8D/EbLtNodzxxx9v14RsQtkq4hOb20H/gysKNo7nRrBTOzhvCVtmZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDfH/ATYspSon588iAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# visualize result of sklearn\n",
    "\n",
    "cat1_ = data[np.where(labels_==0)]\n",
    "cat2_ = data[np.where(labels_==1)]\n",
    "cat3_ = data[np.where(labels_==2)]\n",
    "\n",
    "plt.scatter(cat1_[:,0], cat1_[:,1], color='green')\n",
    "plt.scatter(cat2_[:,0], cat2_[:,1], color='red')\n",
    "plt.scatter(cat3_[:,0], cat3_[:,1], color='blue')\n",
    "plt.title('Hierarchical clustering with k=3')\n",
    "plt.xlim(4, 8)\n",
    "plt.ylim(1, 5)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "La_XZDI5_Bng"
   },
   "source": [
    "---------------------------------------------------------------------------------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "fNl9AY6vAFJG"
   },
   "outputs": [],
   "source": [
    "# kmeans\n",
    "\n",
    "class MyKmeans:\n",
    "    def __init__(self, k, n=20):\n",
    "        self.k = k\n",
    "        self.n = n\n",
    "        \n",
    "    def fit(self, x, centers=None):\n",
    "        # 第一步，随机选择 K 个点, 或者指定\n",
    "        if centers is None:\n",
    "            idx = np.random.randint(low=0, high=len(x), size=self.k)\n",
    "            centers = x[idx]\n",
    "        #print(centers)\n",
    "        \n",
    "        inters = 0\n",
    "        while inters < self.n:\n",
    "            #print(inters)\n",
    "            #print(centers)\n",
    "            points_set = {key: [] for key in range(self.k)}\n",
    "\n",
    "            # 第二步，遍历所有点 P，将 P 放入最近的聚类中心的集合中\n",
    "            for p in x:\n",
    "                nearest_index = np.argmin(np.sum((centers - p) ** 2, axis=1) ** 0.5)\n",
    "                points_set[nearest_index].append(p)\n",
    "\n",
    "            # 第三步，遍历每一个点集，计算新的聚类中心\n",
    "            for i_k in range(self.k):\n",
    "                centers[i_k] = sum(points_set[i_k])/len(points_set[i_k])\n",
    "                \n",
    "            inters += 1\n",
    "\n",
    "        \n",
    "            \n",
    "        return points_set, centers\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "SyLthTXfBfnV"
   },
   "outputs": [],
   "source": [
    "m = MyKmeans(3)\n",
    "points_set, centers = m.fit(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 71
    },
    "colab_type": "code",
    "id": "VE2ryNB-O_Zt",
    "outputId": "55a70e58-fccd-4001-c67c-964ede3a8550"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[5.006     , 3.428     ],\n",
       "       [6.81276596, 3.07446809],\n",
       "       [5.77358491, 2.69245283]])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "centers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 281
    },
    "colab_type": "code",
    "id": "M26gflVYDzY4",
    "outputId": "abb1b7b1-df4f-4fa1-9a24-1dc722112c2c"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEICAYAAABcVE8dAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3df5xcdX3v8dd7fwRYIIlilB9JNloUigoKuSDGq2jSll9Ce7UVG4tYaerGX1h7aa33we+g9mELVkxotAqYVLFULVK0igqKVmz4IUrRXqpsCCyXyI8ABtEkn/vHOZOdnZ3Zc2bn7MyZnffz8ZjHzpzznXM+58zsZ8+e7/d8jiICMzOb/fo6HYCZmbWHE76ZWY9wwjcz6xFO+GZmPcIJ38ysRzjhm5n1CCf8LibpLknHlSCOJZJC0kCD+X8l6RMzuY4p3neGpJtbWXdROv15ZX0Oze4rSfdKWlFMdNYOTvglVe+XqfYXMiJeGBE3tj24JkXExRFxZqfjaEX6x+bgVpbR6c+r+nOY7h/QoknaIGlM0uOS/ktSV39Pys4JvwdN55dcUv9MxNILOp1US+4DwJKImAucAlwk6agOxzRrOeF3ser/AiT1SfpLSf8t6WFJn5P0zHRe5WjurZI2A99Ip/+TpAclbZP0LUkvrFr2FZLWSbpe0i+AV0vaS9LfSBpN33OzpL2qQlopabOkn0t6f9WyzpO0oer1KyR9V9Jjku6TdEY6/SRJt6dHe/dJOq+JfbFI0uclbU23/7I6bSYd1Uq6sXJUKelgSTel2/ZzSVen07+VNv+BpCclvSGdfrKkO9Lt+K6kw2s+m7+QdCfwC0kDNZ/XeelndJWkJ9LTPUur3n9kui+eSD+nqyVd1GDbRytJUtKb0m08LH19pqQv1vkcKtv0WLpNx1Yt78OSHpX0M0kn5Nz/h6btT8vTviIi7oqIpysv08dvNLMMy88Jf/Z4F/C7wKuAA4FHgY/VtHkV8JvA76Svvww8H3g2cBuwsab9HwJrgH2Bm4EPA0cBLweeCZwN7Kpq/wrgEGA5cI6k36wNUtLidL0fBRYALwHuSGf/AjgdmA+cBIxI+t2sDU//+7gOGAWWAAcBn816Xx0XAl8FngEsTGMkIl6Zzj8iIvaJiKslHQl8EvhTYD/g74FrJe1Rtbw3ptsxPyJ21FnfKWmc84FrgcvS7ZkDfAG4gmQ/fwb4vSnivgk4Ln3+SuCnJJ915fVNdd5T2ab56Tb9e/r6GOAnwLOAvwb+QZKmWDfpvvgq8M6I+Gw67br0D2G9x3U1718raTvwY2AMuH6q9VkLIsKPEj6Ae4EngceqHtuBm2varEif3w0sr5p3APBrYIAkCQbwvCnWNz9tMy99fQVwVdX8PuApkqRX+97K8hdWTfs+cFr6/DxgQ/r8fcAXcu6DS4FLatYxUKfdscDWBvPOqOyzessAbgTOTJ9fBayv3o6qdgEcXPV6HXBhTZufAK+q+mz+uM5nWvm8zgNuqJp3GPBU+vyVwP2AqubfDFzUYD+9Fbi26ntwJvDZ9PUocGSdz6HevjgDuKfq9VDaZv8pvqPnA1uAV7f4fe8nOWD4P8BgJ3/3ZvPDR/jl9rsRMb/yAFZP0XYY+ELlKIrkF38n8JyqNvdVnkjql/TB9BTQ4yS/vJAc2U1qn07fE/jvKWJ4sOr5dmCfOm0WNVqGpGMkfTM9LbMNeFtNPI0sAkaj/lF0M84GBHw/PcXyx1O0HQbeW33kmsZxYFWb++q/dbfa/bVnerrpQOD+SDNhjmXdBPxPSfuTJM6rgWWSlgDzGP8PKo/dMUXE9vRpvc+x4m3AdyPim02sY5KI2BkRN5P8ZzXSyrKsMSf82eM+4ITqPxARsWdE3F/VpjqB/CFwKrCCJCksSaerQfufA7+k9fOr902xjH8kObWxKCLmAZfXxDPVMhcru3P0F+nPoapp+1eeRMSDEfEnEXEgyamatWo8Muc+YE3N/h6KiM9UtZluKdox4KCaUymLGjWOiHtI/mC8C/hWRDxBkrhXkfx3s6ve26YZW623kez7S6onSvpy2jdQ7/HlKZY3gM/hzxgn/NnjcmCNpGEASQsknTpF+32Bp4GHSRLgxVMtPE0anwT+VtKB6X8Ix9acs85jI7BC0h+kHZn7SXpJVUyPRMQvJR1N8kcpj++TJMkPStpb0p6SltXZhq0kp0relMb/x1QlF0m/L2lh+vJRkqS4M339/4DnVS3u48Db0v9KlK73JEn75ox5Kv+ervcd6T46FTg64z03Ae9g/Hz9jTWva20l6X95XoP5eT0BHA+8UtIHKxMj4oRI+gbqPU4AkPRsSadJ2if9PH6HpN/jGy3GZA044c8eHyE5Ov6qpCeA75F0wDVyFcn53fuB/0zbZ/lz4IfAfwCPAB+iye9QRGwGTgTemy7jDuCIdPZq4II0/nOAz+Vc5k7gtcDBwGaSc8pvaND8T4D/TfKH7oXAd6vm/Q/gFklPkuzLd0fEz9J55wFXpqdv/iAiNqXLuozkj8M9JOfAWxYRvwL+F8m5+ceAN5F0Sj89xdtuIvmD+a0Gr2vXsZ2kQ/476Ta9rIV4HwN+CzhB0oXNvJXk9M0Wkn34YeCsiPiX6cZiU9PE04RmVkaSbgEuj4hPdToW614+wjcrIUmvkrR/ekrnzcDhwFc6HZd1t1xXAEq6l+Rc3U5gR0QsrZkvklMKJ5J0Hp0REbcVG6pZTzmE5JTWPiSjml4fEWOdDcm6Xa5TOmnCXxoRP28w/0TgnSQJ/xjgIxEx1fljMzNrs6JO6ZxKcpFORMT3gPmSDiho2WZmVoC8RZ2CZPRHAH8fEetr5h/ExAtDtqTTJvwLKmkVydhg9t5776MOPfTQaQVtZtarbr311p9HxILpvDdvwl8WEQ9IejbwNUk/jojq4V71Lo6ZdK4o/UOxHmDp0qWxadOmpgM2M+tlkkan+95cp3Qi4oH050MkRZ1qLwLZwsQrARcCD0w3KDMzK15mwk+vINy38hz4beBHNc2uBU5Przh8GbDNIwrMzMolzymd55AU5aq0/8eI+IqktwFExOUk5UxPJLnacDvwlpkJ18zMpisz4UfETxm/9L16+uVVzwN4e7GhmZlZkXylrZlZj3DCNzPrEU74ZmY9wgnfzKxHOOGbmfUIJ3wzsx7hhG9m1iOc8M3MeoQTvplZj3DCNzPrEU74ZmY9wgnfzKxHOOGbmfUIJ3wzsx7hhG9m1iOc8M3MeoQTvplZj3DCNzPrEbkTvqR+SbdLuq7OvDMkbZV0R/o4s9gwzcysVXluYl7xbuBuYG6D+VdHxDtaD8nMzGZCriN8SQuBk4BPzGw4ZmY2U/Ke0rkUOBvYNUWb10m6U9I1kha1HpqZmRUpM+FLOhl4KCJunaLZl4AlEXE4cANwZYNlrZK0SdKmrVu3TitgMzObnjxH+MuAUyTdC3wWeI2kDdUNIuLhiHg6fflx4Kh6C4qI9RGxNCKWLliwoIWwzcysWZkJPyLeFxELI2IJcBrwjYh4U3UbSQdUvTyFpHPXrDgbN8KSJdDXl/zcuLHTEZl1nWZG6Uwg6QJgU0RcC7xL0inADuAR4IxiwjMjSe6rVsH27cnr0dHkNcDKlZ2Ly6zLKCI6suKlS5fGpk2bOrJu6zJLliRJvtbwMNx7b7ujMesoSbdGxNLpvNdX2lr5bd7c3HQzq8sJ38pv8eLmpptZXU74Vn5r1sDQ0MRpQ0PJdDPLzQnfym/lSli/PjlnLyU/1693h61Zk6Y9SsesrVaudII3a5GP8M3MeoQTvplZj3DCNzPrEU741h4ujWDWce60tZnn0ghmpeAjfJt573//eLKv2L49mW5mbeOEbzPPpRHMSsEJ32aeSyOYlYITvs18h6pLI5iVghN+r6t0qI6OQsR4h2qRSd+lEcxKwfXwe51rzZt1FdfDt+lzh6pZz3DC73XuUDXrGU74vc4dqmY9I3fCl9Qv6XZJ19WZt4ekqyXdI+kWSUuKDNJm0GzqUHX5BrMpNVNa4d3A3cDcOvPeCjwaEQdLOg34EPCGAuKzdpgNteZdvsEsU64jfEkLgZOATzRocipwZfr8GmC5JLUenllOLt9glinvKZ1LgbOBXQ3mHwTcBxARO4BtwH61jSStkrRJ0qatW7dOI1yzBjzayCxTZsKXdDLwUETcOlWzOtMmDfCPiPURsTQili5YsKCJMM0yeLSRWaY8R/jLgFMk3Qt8FniNpA01bbYAiwAkDQDzgEcKjNPKbPVqGBhIOn0HBpLX7ebRRmaZMhN+RLwvIhZGxBLgNOAbEfGmmmbXAm9On78+bdOZS3itvVavhnXrYOfO5PXOncnrdif92TTayGyGNFVaQdJxwJ9HxMmSLgA2RcS1kvYEPg28lOTI/rSI+OlUy3JphVliYGA82Vfr74cdO9ofj9ks10pphabueBURNwI3ps/PqZr+S+D3pxOAdbl6yX6q6WbWMb7S1lrT39/cdDPrGCd8a03l4qa8082sY5zwZ7sVK5JOzMpjxYpil792LYyMjB/R9/cnr9euLXY9LptgJbbxhxtZcukS+s7vY8mlS9j4w+a/n0UsI4vr4c9mK1bA178+efry5XDDDe2PZ7pqyyZAMuTSo3CsBDb+cCOrvrSK7b8e/34ODQ6x/rXrWfnifN/PZpbRSqetE/5sNlV1i24aNeubtFiJLbl0CaPbJn8/h+cNc+9Z9xa+DN8AxWY3l02wEtu8rf73sNH0mVpGHk74Vn4um2Altnhe/e9ho+kztYw8nPBns+XLm5veSFaH6Ux3qLpsgpXYmuVrGBqc+P0cGhxizfL8388ilpFLRHTkcdRRR4XNsA0bIqSI5Ix98pCS6c0sY2ho4jKGhsaXkTW/yG0ZHk7iHx4ufvlmLdhw54YYvmQ4dJ5i+JLh2HBn89/PvMsgqXAwrbzrTtvZrIjOzqxluEPVrK3caWv1FdHZmbUMd6iadQ0n/NmsiM7OrGW4Q9WsazjhT1e7rvxspcO0iM7OrGW4Q9VmUDuuPu0p0z353+qjqztt29lR2WqHaRGdnVnLcIeqzYANd26IoTVDwXnsfgytGZpWh+hsgjtt26xdHZXuMLUeVsQVrLORO23brV0dle4wtR7WrqtPe4kT/nS0q6PSHabWw9p19WkvccKfjnZ1VLrD1HpY264+7SGZCV/SnpK+L+kHku6SdH6dNmdI2irpjvRx5syEWxLtumF21npWroRjjyVg94Njj50Yx+rVyX1npeRnvZuLt2PEkevZW5NWvngl61+7nuF5wwgxPG+4qZLDVkdWry4gYJ/0+SBwC/CymjZnAJc101vc1aN0ymJkJHZVj9CB5PXIyO75UTM/qudHtGfEUbtGNZn1ANo1SkfSEHAzMBIRt1RNPwNYGhHvyLusrh6lUxYDA/VvFt7fDzt2ZM+H9oz08Wgis8LM+CgdSf2S7gAeAr5WneyrvE7SnZKukbSowXJWSdokadPWrVunE69ViXrJvHp6g/kTprdjpI9HE5mVQq6EHxE7I+IlwELgaEkvqmnyJWBJRBwO3ABc2WA56yNiaUQsXbBgQStxG7CrwR2tdk+v3Ge2VvX0doz08Wgis1JoapRORDwG3AgcXzP94Yh4On35ceCoQqIrsyI6IfN0qDYwNjbGx/sGqD0hF8An+gZ48MEHk/vA1lM9fc0aGBycOH9wsLmRPlnb0UWjiVq9lD/P+10uwDolzyidBZLmp8/3AlYAP65pc0DVy1OAu4sMsnQqN9UeHU26IEdHk9fNJP3Vq2HduvHTKzt3Jq9zJv0LL/4gA/strDuvf7+FXHjxB2HZsiQBVxsYSKZXq/1PYap74dbKsx3tGtXUosqNpEe3jRIEo9tGWfWlVbkTcp73t7oOs1ZkdtpKOpzkFE0/yR+Iz0XEBZIuIOktvlbSB0gS/Q7gEZJO3R83XChd3mlbRCdkng7VBsbGxviNQ36Tx598goHYNWn+DvUxb5+5bJu3DwNbtkwdZ6vb0sJ2lE2rl/Lneb/LBVirWum0HchqEBF3Ai+tM/2cqufvA943nQC6UhGdkHk6VBu48OIPMnTYa+i/5Qt15/fHLvY67NUN50+Is9VtaWE7yqbVS/nzvN/lAqyTfKXtdBTRCZmnQ7WOsbExrrjySvZc+nvsVP2Pb6f62HPp73Ffo1Mz1XG2ui3T3I4yavVS/jzvd7kA6yQn/OkoohMyT4dqHZWj+4F9nsnGI46v22m78YjjGdjnmVz0vKN4uvYcfm2crW7LNLejjFq9lD/P+10uwDpquldstfro+itti6gBPzIS0d+fXHna3z/xCtg6Hnjggdhr33lx0NuviuG/uC6G/+K6uGnxEbErvcJ2F8RNi4/YPe+gt18Vl/cPxq6sdbS6LU1uR5m1ejPqPO9ffuXyCTXel1+5vKjwcxu5biT6z+8PziP6z++Pkeu69zPrNbgefm9Y/c5387n/uI99jnsrAKfc9U0++JXLGNrx9O422wf24C+PfwfXvvDVyfzrL2VoV9X59KGhUo6Q6RWr/3U16zatmzR9ZOkIa09a2zMx2PS10mnrhN8lKiNznnn6RxnY55kA3LzuLSx8fPIVy1vmLuAVI59qON8lDTpn4IIBdsbkDu1+9bPjnPaMaipDDDZ9vgFKD6g+d19x4OM/r9u2Mr3RfJc06Jx6iXaq6bM1BuuMzGGZVg5fuvZfeHjzKA9XDbXcDCyp03YzweiHTm443yUNOqdf/Q2PrnspBuuM3j3Cb7U0Qp73t1A6odZ9o/dO6oBZsmEDzJkzseGcOSzZsGF8fpeUNGiHMpQ0WHVU/dFL1dNX/+tqBi4YQOeLgQsGWP2vE783rW5HnhjyrKfV+XmU4TObVabb29vqo6OjdFqtz57n/Xlq0RexHYODE5c/ODgxjiJGE80CG+7cEENrhiaMjhlaM9T0KJwiTDVCZuS6kQkxVh6VNkVtR9Yonaz1tDo/jzJ9ZmWCR+k0qdVyAnne346SA64zn1u3lDTI6lBt13ZkrafV+UXE0KvcadusVssJ5Hl/O0oOuM58bt1S0iCrQ7Vd25G1nlbnFxGDNa83E36r5QTyvL8dJQdcZz63bilp0KjjtDK9XdvRaHkH7XNQrjiKiLNbPrNu0psJv9VyAnne346SA11UZ77TuqWkQVaHaru2o956BnbCi8YOzRVHEXF2y2fWVaZ78r/VR8dLK7SjnEBWmzwxFLEMi4jWyya0S1bphSK2I095h8tuuiz63qPQucTwuYrLzt4jnjl3rxgbG4uIiMMuO2zCMg677LDC4+yWz6ydcKdtm1VugLJ9+/i0ZksW5FlG5eYitUZGYK0vgZ+NKjdI2f7r8e/F0OAQ61+7npUvLqYcxoqrVvD1n3190vTlz13ODaffsPv1e965Gm7/NJesGD8R8J4bdqEjT+fOpT/JtQwrnksrtFsRo2PKMtLHSqUdI1N0fuM7msW5ST4YGxvjhYf8Bnf9ST8H7Due8Mee2MWLPrGTR/7sqcxl2MzwKJ12K2J0TFlG+liplGVkyl9ffCFvPnxisgc4YN8+Tn9xP5PqcltXcMKfjiJGx5RlpI+VShlGpoyNjXHllVdw9jH15zeabuWX5ybme0r6vqQfSLpL0vl12uwh6WpJ90i6RdKSmQg2tzxlD1oprVDE6Jg1ayYn7v7+5kf6tFoiogBFhJBVhaKQdWSULIDsS/nzLKMVeUamrLhqBTpfux8rrlrR1HYsf+7yuuuuTK8c3X9j3x0s4Qn6eJwlPMFGfgUkR/mLHlbdo/xGy26kHeUZitAtcWbJc4T/NPCaiDgCeAlwvKSX1bR5K/BoRBwMXAJ8qNgwm1DpDB0dTYoNjI4mr6szRJ42U1m5MulcHR5OMtTwcPM15r/zncmnZnbuTKZXLFuWZLhqfX3J9CK2owBFhFDpm67sjp07k9eVpF/IOtIa8JULmHbGTtZtWjchYVc6TEe3jRIEo9tGWfWlVbt/efMso1UrX7yS9a9dz/C8YYQYnjc8ocO2Xofr13/29QlJP2s7XrDfC+qu+wX7vWD30f3By37NKn7JqIIQjCpYxS93J/1b5uxNf01XQ7MdtllxZs1vl26JM4+mOm0lDQE3AyMRcUvV9H8DzouIf5c0ADwILIgpFj5jnbZ5OkPLUJIgT4dsVpwl2I4iQsjaFYWsI0cN+KwO0zLUkc/T4drKdrxz6yq4/dN8YcUvGNXkX9/hEPeyLzA+Yudv/+5j09qWdpRnKELZ4pzxTltJ/ZLuAB4Cvlad7FMHAfcBRMQOYBuwX53lrJK0SdKmrVvr3JijCHk6Q8tQkiBPh2xWnCXYjiJCyNoVhawjRw34rA7Tbqkj38p2VM7db27QK1s9/exj4MorP8WDDz44I3GWpQO7W+LMI1fCj4idEfESYCFwtKQX1TSpd9gx6RsTEesjYmlELF2wYEHz0eaRpzO0DCUJ8nTIZsVZgu0oIoSsXVHIOjJKFkB2h2meZZTBdLdDod0jcxbX/ZVmwvTKiJ2/vvjCGYmzDB3YeeIoS5x5NDVKJyIeA24Ejq+ZtQVYBJCe0pkHPFJAfM3L06FahpIEeTpks+IswXYUEULWrihkHTlqwGd1mOatIz+TsjpcYfrbMXCHdo/AWcMeDNUcsg1FMr1aK0f57SjPUIRuiTOXrEtxgQXA/PT5XsC3gZNr2rwduDx9fhrwuazlzmhphSJKFrRDnhiytqUEpRWKCGH58oll/ZfXXOlfxMeVVQM+T5siyh5ktcman6csQtZ21M4//OzD4qxl+0ScO3f3Y8O5e8bwueOlFTacu+eE+ZXHWcv2ife8c/XUO7+BVvdFu0ovlCWOiNZKK+RJ+IcDtwN3Aj8CzkmnXwCckj7fE/gn4B7g+8Dzspbb1TdAsUJlfRzt+rjacdOPst445LmLDwqS07DTejx38UHT2eUt6dUbpLSS8HuztEIJRrfYuLIMRmrHTT9845Di9Mp21nJphWaVYHSLjSvLYKR23PTDNw4pTq9sZ5F6M+GXYHSLjSvLYKRWR2PkGa3hG4cUp1e2s0i9mfBLMLrFxq1ZA4ODE6cNDk4cjJRVhQJaL7+QZzRGX82vTB99E+YP9k3ckMG+wQmjNbLaZK0Dsi/jL2rUSNnLBeTdznZsR9n3VUVvJvwiSiNYoaTGr/NUofjYxx7lj/5oe0vlF7LKGnxn83fYxa4J79nFLr6zeTwQ1WxI7eusNlnryHMZf9Z25NEN5QLybGc7tqMb9lVFb3baWqlkdcrmqUKx79yHefKJSRd3F9qxm1VaoYhO2yLWUYTZ0iHaju2YdaUVzGZSVqdsVumFsbExnnziGU0tezqySisU0WlbxDqKMFs6RNuxHd20r5zwreOyOmWzSi9c9IGL6Nvz/qaWPR1ZpRWK6LQtYh1FmC0dou3Yjm7aV0741vGa+mvWwJw5E6fNmTPeKTtV6YWxsTGuuPIKnv36S6Hm3Hdl2c2YqvMtq7RCnk7ENcvXMKd/4sbO6Z+Tu3xDuy7j76pyAVNox3Z0075ywu91JaipD8mqG71euza5b3vliL6/f/w+7hd94CLmvXweD3/jT6lXw+/ii/PHkNX5tvaktYwsHdl9tN2vfkaWjrD2pOSG8nk7S2v7zapfL1u8rO4onWWLlzW1jla1az0zrR3b0U37yp22va4EVx1PN4SxsTEOPvRgFl2wiJ+cdTf1i7ZO/mPSMI4SdPDNls5SmznutLXpK8FVx9MNoXJ0Pzh/cOqGeeMoQQdfN3UAWvdxwu91JbjqeDohVM7dzz1+bsbS8/8HW4YOvm7qALTu44Tf60pw1fF0Qqg9uh888P8yObkHz3hG/dE7deMoQQdfN3UAWvdxwu91bbrqeKqBQHlCqH7/woU7+PjHt084uj/k4tfRN/9Bqqv2au4D/GrXoblvzpH3ys1WLqHPWkc3dQDauG4preBOW5txlYFA27ePTxsayv93pd776dvOwjPPZ/7Lrwfgse+eyP1XnEf8aq/dTTTnKeYe+l7edFwfl33ksta3Ix3Fs/3X44EMDQ45Ife4dn8vWum0dcK3GdfqQKBG7x/c7wEO+ZvfAeAn7/03fv3wgZPaDDzjfvbYdQj3/Pge9t9//6binhSHR9BYHS6tYFal1YFAjdr9+uH96z6vtuPRA5h77Fwu+sBF+VY2VRweQWN1dNP3wgnfZlyrA4EatRvc78G6z2vbzD1+LldcecW0brQ9IQ6PoLE6uul7kZnwJS2S9E1Jd0u6S9K767Q5TtI2SXekj3NmJtwe1GrZgw6XTYDs0gkwdZj16uXT/yue87qP7H75nNd9BM15akITzXmK57zuIwzOHyzkKL+oETSrVycVQKXk5+rVLYU1Ld3SydgNumpkVdZNb4EDgCPT5/sC/wUcVtPmOOC6Zm6m29GbmHeLVu/eXZKbtW/YEDE4ODGMwcH8NynfsCFizpyJ8+GXAW+suZn2GwN+FrAz/Tlx/sLhha1vy50bYviS4dB5iuFLhpu+YfbISO12JI+RkZZDy61Xb/49k1r9XjSDdt7EXNK/AJdFxNeqph0H/HlEnJx3Oe60zWGmejvbfLP2Vm9SXpLNKESe2v4zzZ3P3a1to3QkLQG+BbwoIh6vmn4c8M/AFuABkuR/V533rwJWASxevPio0Xq/xTaur69+IRgJdk2uDFn4+wuSFUar87tJnRtg7dauAXN95/cRda5AFmLXuV22Q3tQW0bpSNqHJKmfVZ3sU7cBwxFxBPBR4Iv1lhER6yNiaUQsXbBgwXTi7S0z1dvZ5pu1t3qT8pJsRiGyavu3Qzd1MlqxciV8SYMkyX5jRHy+dn5EPB4RT6bPrwcGJT2r0Eh7UatlD0pQNiFPGK3O7yZT1fZvl67qZLRiZZ3kJ6k5exVw6RRt9mf89NDRwObK60YPd9rmNDIS0d+f9Oz19zffu7dhQ8TwcISU/Gxzh23F8uUTOymXL584PyvMkmxGIVr9SIvQzk5GKxYz2Wkr6RXAt4EfMn5Lob8CFqd/MC6X9A5gBNgBPAX8WUR8d6rlutM2h1ZrEpTE6tWwbt3k6ZWbmJhZfi6tMFvNkuEpZRiZYjZbuLTCbFWCm5MUoV6yn2q6mc0MJ/wymyXDU8owMsXMnPAbK0FJglzDU+MCh+0AAAlWSURBVMoQZ4YyjEwpky74yGy2mm5vb6uPUo/SKUlJgt2xNBqeUqY4p7BhQ0Rf38Qw+/pKF2ZbdMlHZiVGO0srFKXUnbbd0lnaJXF2SZht4X1hrfIonaJ1y7X8XRJnl4TZFt4X1iqP0ilat3SWdkmcXRJmW3hfWCc54dfTLdfyd0mcXRJmW3hfWEdN9+R/q49Sd9pGdM+1/F0SZ5eE2ZZKFt2yL6yccKetWetaLQExSyphWMm509asAK2WgPAIHGsHd9qaFaDVEhCzpBKGzWJO+GapVktAeASOlZ0Tvlmq1RIQHoFjZeeEb5ZauzbpoK0c0ff3N1ezf+XKpIN2eDi5kGp42B22Vi7utDUz6yLutDUzs0xO+GZmPSIz4UtaJOmbku6WdJekd9dpI0l/J+keSXdKOnJmwrVJXFzdzHIayNFmB/DeiLhN0r7ArZK+FhH/WdXmBOD56eMYYF3602ZS7aWdo6PjQ0rcU2hmNTKP8CNiLCJuS58/AdwNHFTT7FTgqrTUw/eA+ZIOKDxam+j97594HT8kr9///s7EY2al1tQ5fElLgJcCt9TMOgi4r+r1Fib/UUDSKkmbJG3aunVrc5HaZL6008yakDvhS9oH+GfgrIh4vHZ2nbdMGu8ZEesjYmlELF2wYEFzkdpkvrTTzJqQK+FLGiRJ9hsj4vN1mmwBFlW9Xgg80Hp4NiVf2mlmTcgzSkfAPwB3R8TfNmh2LXB6OlrnZcC2iBgrME6rx5d2mlkT8ozSWQb8EfBDSXek0/4KWAwQEZcD1wMnAvcA24G3FB+q1bVypRO8meWSmfAj4mbqn6OvbhPA24sKyszMiucrbc3MeoQTvplZj3DCNzPrEU74ZmY9wgnfzKxHOOGbmfUIJ3wzsx7hhG9m1iOc8M3MeoQTvplZj3DCNzPrEU74ZmY9wgnfzKxHOOGbmfUIJ3wzsx7hhG9m1iOc8M3MeoQTvplZj8hzE/NPSnpI0o8azD9O0jZJd6SPc4oP08zMWpXnJuZXAJcBV03R5tsRcXIhEZmZ2YzIPMKPiG8Bj7QhFjMzm0FFncM/VtIPJH1Z0gsLWqaZmRUozymdLLcBwxHxpKQTgS8Cz6/XUNIqYBXA4sWLC1i1mZnl1fIRfkQ8HhFPps+vBwYlPatB2/URsTQili5YsKDVVZuZWRNaTviS9pek9PnR6TIfbnW5ZmZWrMxTOpI+AxwHPEvSFuBcYBAgIi4HXg+MSNoBPAWcFhExYxGbmdm0ZCb8iHhjxvzLSIZtmplZiflKWzOzHuGEb2bWI5zwzcx6hBO+mVmPcMI3M+sRTvhmZj3CCd/MrEc44ZuZ9QgnfDOzHuGEb2bWI5zwzcx6hBO+mVmPcMI3M+sRTvhmZj3CCd/MrEc44ZuZ9QgnfDOzHuGEb2bWI5zwzcx6RGbCl/RJSQ9J+lGD+ZL0d5LukXSnpCOLD9PMzFqV5wj/CuD4KeafADw/fawC1rUelpmZFS0z4UfEt4BHpmhyKnBVJL4HzJd0QFEBmplZMQYKWMZBwH1Vr7ek08ZqG0paRfJfAMDTjU4TlcyzgJ93OogcHGexuiHObogRHGfRDpnuG4tI+KozLeo1jIj1wHoASZsiYmkB659RjrNYjrM43RAjOM6iSdo03fcWMUpnC7Co6vVC4IEClmtmZgUqIuFfC5yejtZ5GbAtIiadzjEzs87KPKUj6TPAccCzJG0BzgUGASLicuB64ETgHmA78Jac614/jXg7wXEWy3EWpxtiBMdZtGnHqYi6p9vNzGyW8ZW2ZmY9wgnfzKxHtCXhS+qXdLuk6+rM20PS1WlphlskLWlHTPVkxHmGpK2S7kgfZ3Yoxnsl/TCNYdLwrLKUusgR53GStlXtz3M6EON8SddI+rGkuyUdWzO/LPsyK84y7MtDqtZ/h6THJZ1V06bj+zNnnB3fn2kc75F0l6QfSfqMpD1r5jedO4sYh5/Hu4G7gbl15r0VeDQiDpZ0GvAh4A1tiqvWVHECXB0R72hjPI28OiIaXSBSXeriGJJSF8e0K7AaU8UJ8O2IOLlt0Uz2EeArEfF6SXOAoZr5ZdmXWXFCh/dlRPwEeAkkB07A/cAXapp1fH/mjBM6vD8lHQS8CzgsIp6S9DngNJJSNxVN584ZP8KXtBA4CfhEgyanAlemz68BlkuqdzHXjMoRZ7dwqYscJM0FXgn8A0BE/CoiHqtp1vF9mTPOslkO/HdEjNZM7/j+rNEozrIYAPaSNEDyR772+qamc2c7TulcCpwN7Gowf3dphojYAWwD9mtDXLWy4gR4Xfqv6DWSFk3RbiYF8FVJtyopVVGrUamLdsuKE+BYST+Q9GVJL2xncMDzgK3Ap9LTeJ+QtHdNmzLsyzxxQmf3Za3TgM/UmV6G/VmtUZzQ4f0ZEfcDHwY2k5Sp2RYRX61p1nTunNGEL+lk4KGIuHWqZnWmtXWsaM44vwQsiYjDgRsY/8vabssi4kiSf4/fLumVNfM7vj9TWXHeBgxHxBHAR4Evtjm+AeBIYF1EvBT4BfCXNW3KsC/zxNnpfblbesrpFOCf6s2uM60j48Iz4uz4/pT0DJIj+OcCBwJ7S3pTbbM6b51yf870Ef4y4BRJ9wKfBV4jaUNNm92lGdJ/XeYxdXXOmZAZZ0Q8HBFPpy8/DhzV3hB3x/FA+vMhknOPR9c0KUWpi6w4I+LxiHgyfX49MCjpWW0McQuwJSJuSV9fQ5JYa9t0el9mxlmCfVntBOC2iPh/deaVYX9WNIyzJPtzBfCziNgaEb8GPg+8vKZN07lzRhN+RLwvIhZGxBKSf5++ERG1f6WuBd6cPn992qatf/XzxFlzrvEUks7dtpK0t6R9K8+B3wZqK452vNRFnjgl7V853yjpaJLv4sPtijEiHgTuk1SpPLgc+M+aZh3fl3ni7PS+rPFGGp8m6fj+rNIwzpLsz83AyyQNpbEsZ3LOaTp3tmuUzgSSLgA2RcS1JJ1Rn5Z0D8lfp9M6EVM9NXG+S9IpwA6SOM/oQEjPAb6QfhcHgH+MiK9Iehu0XOqi3XG+HhiRtAN4Cjit3X/ogXcCG9N/738KvKWE+zJPnGXYl0gaAn4L+NOqaaXbnzni7Pj+jIhbJF1DcnppB3A7sL7V3OnSCmZmPcJX2pqZ9QgnfDOzHuGEb2bWI5zwzcx6hBO+mVmPcMI3M+sRTvhmZj3i/wOdLNk3yalUlAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# visualize result\n",
    "\n",
    "cat1 = np.asarray(points_set[0])\n",
    "cat2 = np.asarray(points_set[1])\n",
    "cat3 = np.asarray(points_set[2])\n",
    "\n",
    "for ix, p in enumerate(centers):\n",
    "    plt.scatter(p[0], p[1], color='C{}'.format(ix), marker='^', edgecolor='black', s=256)\n",
    "        \n",
    "plt.scatter(cat1_[:,0], cat1_[:,1], color='green')\n",
    "plt.scatter(cat2_[:,0], cat2_[:,1], color='red')\n",
    "plt.scatter(cat3_[:,0], cat3_[:,1], color='blue')\n",
    "plt.title('Hierarchical clustering with k=3')\n",
    "plt.xlim(4, 8)\n",
    "plt.ylim(1, 5)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "HiFFoBdWN4fW"
   },
   "outputs": [],
   "source": [
    "# using sklearn\n",
    "from sklearn.cluster import KMeans\n",
    "kmeans = KMeans(n_clusters=3, max_iter=100).fit(data)\n",
    "gt_labels__ = kmeans.labels_\n",
    "centers__ = kmeans.cluster_centers_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 143
    },
    "colab_type": "code",
    "id": "LgKRAwmxObYS",
    "outputId": "032bcef5-ba68-4707-fbb0-f7a225ee968f"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 1, 1, 1, 1, 0, 0, 0, 2, 0, 2, 0, 2, 0, 2, 2, 2, 2, 2, 2, 0,\n",
       "       2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 0, 2,\n",
       "       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0,\n",
       "       0, 0, 0, 2, 2, 0, 0, 0, 0, 2, 0, 2, 0, 2, 0, 0, 2, 2, 0, 0, 0, 0,\n",
       "       0, 2, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2])"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gt_labels__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 71
    },
    "colab_type": "code",
    "id": "A0iu18HPOcrH",
    "outputId": "5794f33c-4ebd-47dc-d351-05f44c17343d"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[6.81276596, 3.07446809],\n",
       "       [5.006     , 3.428     ],\n",
       "       [5.77358491, 2.69245283]])"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "centers__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 281
    },
    "colab_type": "code",
    "id": "wEfO5JVjOC5p",
    "outputId": "a6386044-2c7b-420d-f429-0b4960900f83"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEICAYAAABcVE8dAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3de5gcdZ3v8fdnLgEGSIIQAQmZuKJw8C5zuGx23Wjiioh4fHCPuFGER0/WiRdc2dWjnsPV4OXZVVwROEFXwOBtcXURWVdQUcEVN1wEEd1FzUBkkMglgEEgyff8UTVJT6d7qnq6prt66vN6nn7SXVVd/a2azndq6vurbykiMDOz2a+v2wGYmVlnOOGbmVWEE76ZWUU44ZuZVYQTvplZRTjhm5lVhBN+iUlaL2l5t+PoJkkrJH2rw595hqS1rc4rK0m3S1o6xfxrJb0l57qWStpQWHDWUU74VmoRcVlE/Hm34+hlEfHsiLgWyvELS9KhktZJejB9XCPp0G7GVBVO+GYlIGmg2zF00D3Aa4GnAPsAVwBf7GpEFeGE3yMkHSLp15JOSF+vl/S3km6V9HtJn5G0r6R/lfRIetS0V837j5T0Q0kPSfpJ7Z/4kk6WdEf6vl9J+quaeUslbZB0qqT7JI1LOrlm/jGSfpa+9zeS/qZJ/JOOLCUtlhQTiU7SSelnP5Ju54qa6dfVvC8kvVXSf6VHh5+SpHRev6S/l/S7dB1vr/2MBjG9N435EUm/kLSswTKDkr4g6SuS5jSY3+5+fa+ke4HPZu3rus99iaTbal5fI+nHNa+vk/Q/0ufrJS2XdDTwfuB1kh6V9JOaVQ5Luj6N9VuS9mn0uQ3ieGf681+YZ3mAiHgoItZHcpm/gK3AQXnfb22ICD9K+gDWA8uBFwF3AcfWzfsRsC9wAHAfcBPwQmAX4DvA6emyBwD3A8eQ/JJ/Wfp6QTr/lcAzSP7z/RmwGXhROm8psAU4CxhM17EZ2CudPw78afp8r4n3NdiWM4C1Na8XAwEMALsDDwMHp/P2B56dPj8JuK7mfQFcCcwHFgEbgaPTeW8FfgYsTGO5ZuIzGsRzMHA38LSaeJ5RGyuwG/AN4GKgv347CtqvH0l/Xrtl7eu6+HcFHiM5Qh4A7iU5ct4zXddjwN6136NGP4d02rXAL4Fnpe+9Fvhwk5/jUmBD+vz/knznJrZ3EfDQFI+/rFvXQ+n2bgP+T7f/v1Xh4SP88vtTkj953xQRV9bN+2RE/DYifgP8ALghIm6OiMeBr5Ikf4A3AFdFxFURsS0irgbWkSQUIuIbEfHLSHwP+Fb6uROeBM6KiCcj4irgUZKEOTHvUElzI+LBiLhpmtu5DXiOpN0iYjwibp9i2Q9HcpR4F/Bd4AXp9P8JfCIiNkTEg8CHp1jHVpJEe6ikwUiOOH9ZM38u8E2SRHhyRGxtsI529+s2kl/Kj0fEY+m0qfb1dhHxh/SzXgyMALcC1wFLgCOB/4qI+6fY/nqfjYj/TOP4Mjv2aSOS9DHg5cBLImJjGtNdETF/isfn67ZhPjAPeDtwcwux2jQ54ZffW4EfRsR3G8z7bc3zxxq83iN9Pgz8RXra4SFJDwF/QnIkjaRXSPqRpAfSeceQHDlOuD8ittS83lyz7uPT5cckfU/SUa1uYET8Hnhduq3jkr4h6ZAp3nJvk1ieRnLUPqH2ef1n3gm8i+SI9z5JX5T0tJpFjgSeR/LLpVmHwXb368Y0cdeaal/X+x7JEfeL0+fXkvwl8Wfp61Y026eNzAdWAh+KiE0tfs4k6c/+QuBSSU9tZ12WzQm//N4KLJL08TbWcTfwubqjrd0j4sOSdgG+AvwdsG961HUVyWmITBHxHxHxauCpwNdIjg4b+T0wVPN6v7r1/FtEvIwkWf4cuKiF7ZswTnI6Z8KBUy0cEZ+PiD8hSdxBcnplwreADwHflrRvk1W0u1/bbVVbn/C/R3bCL6I97oPAsSR1hyUTEyUtSmsDzR4rmqyvj+S7cUABsdkUnPDL7xHgaODFkqY6RTGVtcCrJL08LWzumhYIFwJzSE5tbAS2SHoFkGsYpKQ5SsbJz4uIJ0nOwzc69QFwS7oNiyTNA95Xs559JR0naXfgcZLTGM3WM5UvA6dIOkDSfOC9U8R+sKSXpon5DyR/EU36zIj4KPB5kqTfqIg5I/u1BT8kOd1zOPDj9DTYMHAE8P0m7/ktsFhSW//3IxnmuQL4qqQj0ml3RcQeUzwuA5D0MkkvTPfZXOBjJL9E7mgnJsvmhN8DIuIhkoLgKySdPY333w28mmSExkaSI9O/Bfoi4hHgnSTJ8kHgL0lqBnm9EVgv6WGSv0be0CSGq4EvkZxrvpGk8DqhDziVpOj4AMkR6qoWYphwEcmR+a0k54SvIikKNvrlsQvJOf7fkZzOeCrJ/qmP+2ySv1yukfSUunkzuV8zpadDbgJuj4gn0sn/DoxFxH1N3vZP6b/3S5puvWXi868GTgaukHRYC2+dD3wB2ERSIzmIpPBef3rLCqbmpyfNelt6VH1hRAx3OxazMvARvs0aknZTcl3AgKQDgNNJRiuZGTmP8CWtJzmXvBXYEhEjdfMFfIId44ZPamN4ntm0SBoiKVYeQnJO/hvAKRHxcFcDMyuJVi7nfklE/K7JvFcAz0wfRwAXpP+adUxEbAb+e7fjMCurok7pvBq4NL3A5EfAfEn7F7RuMzMrQN4j/AC+JSmA/xcRa+rmH8Dki1w2pNPGaxeStJLkgg123333ww45ZKpra8zMrN6NN974u4hYMJ335k34SyLinvRKuKsl/Twiasf5NrpIZ6fiQPqLYg3AyMhIrFu3ruWAzcyqTNLYdN+b65RORNyT/nsfyaiHw+sW2cDkqxoXkoypNjOzkshM+JJ2l7TnxHOSqwV/WrfYFcCJShwJbIqIcczMrDTynNLZl+Ty6YnlPx8R35T0VoCIuJDkisZjgDtJhmU27OFtZmbdk5nwI+JXwPMbTL+w5nkAbys2NDMzK5KvtDUzqwgnfDOzinDCNzOrCCd8M7OKcMI3M6sIJ3wzs4pwwjczqwgnfDOzinDCNzOrCCd8M7OKcMI3M6sIJ3wzs4pwwjczqwgnfDOzinDCNzOrCCd8M7OKcMI3M6sIJ3wzs4rInfAl9Uu6WdKVDeadJGmjpFvSx1uKDdPMzNqV5ybmE04B7gDmNpn/pYh4e/shmZnZTMh1hC9pIfBK4NMzG46Zmc2UvKd0zgXeA2ybYpnjJd0q6XJJB7YfmpmZFSkz4Us6FrgvIm6cYrGvA4sj4nnANcAlTda1UtI6Ses2btw4rYDNzGx68hzhLwGOk7Qe+CLwUklraxeIiPsj4vH05UXAYY1WFBFrImIkIkYWLFjQRthmZtaqzIQfEe+LiIURsRg4AfhORLyhdhlJ+9e8PI6kuGtWnMsug8WLoa8v+feyy7odkVnPaWWUziSSzgLWRcQVwDslHQdsAR4ATiomPDOS5L5yJWzenLweG0teA6xY0b24zHqMIqIrHzwyMhLr1q3rymdbj1m8OEny9YaHYf36Tkdj1lWSboyIkem811faWvnddVdr082sISd8K79Fi1qbbmYNOeFb+a1eDUNDk6cNDSXTzSw3J3wrvxUrYM2a5Jy9lPy7Zo0LtmYtmvYoHbOOWrHCCd6sTT7CNzOrCCd8M7OKcMI3M6sIJ3zrDLdGMOs6F21t5rk1glkp+AjfZt4HPrAj2U/YvDmZbmYd44RvM8+tEcxKwQnfZp5bI5iVghO+zXxB1a0RzErBCb/qJgqqY2MQsaOgWmTSd2sEs1JwP/yqc695s57ifvg2fS6omlWGE37VuaBqVhlO+FXngqpZZeRO+JL6Jd0s6coG83aR9CVJd0q6QdLiIoO0GTSbCqpu32A2pVZaK5wC3AHMbTDvzcCDEXGQpBOAjwCvKyA+64TZ0Gve7RvMMuU6wpe0EHgl8Okmi7wauCR9fjmwTJLaD88sJ7dvMMuU95TOucB7gG1N5h8A3A0QEVuATcDe9QtJWilpnaR1GzdunEa4Zk14tJFZpsyEL+lY4L6IuHGqxRpM22mAf0SsiYiRiBhZsGBBC2GaZfBoI7NMeY7wlwDHSVoPfBF4qaS1dctsAA4EkDQAzAMeKDBOK7NVq2BgICn6DgwkrzvNo43MMmUm/Ih4X0QsjIjFwAnAdyLiDXWLXQG8KX3+2nSZ7lzCa521ahVccAFs3Zq83ro1ed3ppD+bRhuZzZCWWitIWgr8TUQcK+ksYF1EXCFpV+BzwAtJjuxPiIhfTbUut1aYJQYGdiT7Wv39sGVL5+Mxm+Xaaa3Q0h2vIuJa4Nr0+Wk10/8A/MV0ArAe1yjZTzXdzLrGV9pae/r7W5tuZl3jhG/tmbi4Ke90M+saJ/zZbvnypIg58Vi+vNj1n38+jI7uOKLv709en39+sZ/jtglWYpfddhmLz11M35l9LD53MZfd1vr3s4h1ZHE//Nls+XL49rd3nr5sGVxzTefjma76tgmQDLn0KBwrgctuu4yVX1/J5id3fD+HBodY86o1rHhuvu9nK+top2jrhD+bTdXdopdGzfomLVZii89dzNimnb+fw/OGWf+u9YWvwzdAsdnNbROsxO7a1Ph72Gz6TK0jDyd8Kz+3TbASWzSv8few2fSZWkceTviz2bJlrU1vJqtgOtMFVbdNsBJbvWw1Q4OTv59Dg0OsXpb/+1nEOnKJiK48DjvssLAZtnZthBSRnLFPHlIyvZV1DA1NXsfQ0I51ZM0vcluGh5P4h4eLX79ZG9beujaGPz4cOkMx/PHhWHtr69/PvOsg6XAwrbzrou1sVkSxM2sdLqiadZSLttZYEcXOrHW4oGrWM5zwZ7Miip1Z63BB1axnOOFPV6eu/GynYFpEsTNrHS6o2gzqxNWnlTLdk//tPnq6aNvJQmW7BdMiip1Z63BB1WbA2lvXxtDqoeAMtj+GVg9NqyA6m+CibYd1qlDpgqlVWBFXsM5GLtp2WqcKlS6YWoV16urTKnHCn45OFSpdMLUK69TVp1XihD8dnSpUumBqFdaxq08rJDPhS9pV0o8l/UTS7ZLObLDMSZI2SrolfbxlZsItiU7dMDvrc1asgKOOImD7g6OOmhzHqlXJfWel5N9GNxfvxIgj97O3Fq147grWvGoNw/OGEWJ43nBLLYetgayqLiBgj/T5IHADcGTdMicB57VSLe7pUTplMToa22pH6EDyenR0+/yomx+18yM6M+KoU6OazCqATo3SkTQEXAeMRsQNNdNPAkYi4u1519XTo3TKYmCg8c3C+/thy5bs+dCZkT4eTWRWmBkfpSOpX9ItwH3A1bXJvsbxkm6VdLmkA5usZ6WkdZLWbdy4cTrxWo1olMxrpzeZP2l6J0b6eDSRWSnkSvgRsTUiXgAsBA6X9Jy6Rb4OLI6I5wHXAJc0Wc+aiBiJiJEFCxa0E7cB25rc0Wr79In7zNarnd6JkT4eTWRWCi2N0omIh4BrgaPrpt8fEY+nLy8CDiskujIrogiZp6DaxPj4OP/YJ+pPyAXw2X5x7733JveBbaR2+urVMDg4ef7gYGsjfbK2o4dGE7V7KX+e97tdgHVLnlE6CyTNT5/vBiwHfl63zP41L48D7igyyNKZuKn22FhSghwbS163kvRXrYILLthxemXr1uR1zqT/0XPO5pB9RP0xvoCD9xYfPedsWLIkScC1BgaS6ZPepKlfTyXPdnRqVFObJm4kPbZpjCAY2zTGyq+vzJ2Q87y/3c8wa0dm0VbS80hO0fST/IL4ckScJekskmrxFZI+RJLotwAPkBR1f950pfR40baIImSegmoT4+PjPPvgZ3D/o4+hBj++EOyz5278du7eDGzYMHWc7W5LG9tRNu1eyp/n/W4XYO1qp2g7kLVARNwKvLDB9NNqnr8PeN90AuhJRRQh8xRUm/joOWfzpuf1o+sbz1fAic/tp//6BskeJsfZ7ra0sR1l0+6l/Hne73YB1k2+0nY6iihC5imoNjA+Ps4ll1zMe46Anc7nTBC85wjY0OzUTG2c7W7LNLejjNq9lD/P+90uwLrJCX86iihC5imoNjBxdL//nn1wWJM/0A4bYP89+7j2oDk8UX8Ovz7OdrdlmttRRu1eyp/n/W4XYF013Su22n30/JW2RfSAHx2N6O9Prjzt7598BWwD99xzT+y1525xz7v3iDh9bvJ4et1Nyp+u7fPuefcecdFAX2zL+ox2t6XF7Sizdm9Gnef9yy5ZNqnH+7JLlhUVfm6jV45G/5n9wRlE/5n9MXpl7/7Mqgb3w6+Gv37HKrj5c3x8efqH2W1PwNf/AE/WLDQIvGpXeO4cuO0JnvjaH5izrWb+0FApR8hUxapvrOKCdRfsNH10ZJTzX3l+ZWKw6WunaOuE3yMmRubc/r/S0zkA5z4Cmxr8/OYJ3rVn8/luadA1A2cNsDV2Lmj3q58tp3VmVFMZYrDp8w1QKmDSufsJjZJ57fRm893SoGsaJdqpps/WGKw7ModlWjn8yxVX8Ou7HuXcmqGYvwYWN1h2PfD0Mx9uOt8tDbqnX/1Nj66rFIN1R3WP8NttjZDn/W20Tqj3q7ENOxVgFq9dC3PmTF5wzhwWr127Y36PtDTohDK0NFh5WOPRS7XTV31jFQNnDaAzxcBZA6z6xuTvTbvbkSeGPJ/T7vw8yvAzm1WmW+1t99HVUTrt9mfP8/48veiL2I7BwcnrHxycHEcRo4lmgbW3ro2h1UOTRscMrR5qeRROEaYaITN65eikGCceE8sUtR1Zo3SyPqfd+XmU6WdWJniUTovabSeQ5/2daDngPvO59UpLg6yCaqe2I+tz2p1fRAxV5aJtq9ptJ5Dn/Z1oOeA+87n1SkuDrIJqp7Yj63PanV9EDNa6aib8dtsJ5Hl/J1oOuM98br3S0qBZ4XRieqe2o9n6DtjjgFxxFBFnr/zMekk1E3677QTyvL8TLQd6qM98t/VKS4OsgmqntqPR57Cln0PGn50rjiLi7JWfWU+Z7sn/dh9db63QiXYCWcvkiaGIdVhEtN82oVOyWi8UsR152juc973zQn+t4HSi/7QFMf/db42hPefH+Ph4REQcet6hk9Zx6HmHFh5nr/zMOgkXbTts4gYomzfvmNZqy4I865i4uUi90VE435fAz0YTN0jZ/OSO78XQ4BBrXrWGFc8tph3G8kuX8+1ff3un6cuevoxrTrxm++tV7ziFL//H3eyx9M3bpz167Wd43eGL+MXIT3Otw4rn1gqdVsTomLKM9LFS6cTIFJ3Z/I5mcXqSD8bHx3nGwf+Np5z4SQb2eMr2+VsefYAHL30nm099KHMdNjM8SqfTihgdU5aRPlYqZRmZcvY5H2bo0JdOSvYAA3s8hd0OfQk73UzZeoIT/nQUMTqmLCN9rFTKMDJlfHyciy+5hF1HXtNwfrPpVn55bmK+q6QfS/qJpNslndlgmV0kfUnSnZJukLR4JoLNLU/bg3ZaKxQxOmb16p0Td39/6yN92m0RUYAiQsjqQlHIZ2S0LIDsS/nzrKMdeUamLL90OTpT2x/LL13e0nYse/qyhp89MX3i6P4P837Chl1OZmzXV7Fhl5N5tP+7QHKU3/+7fRoe5TdbdzOdaM9QhF6JM0ueI/zHgZdGxPOBFwBHSzqybpk3Aw9GxEHAx4GPFBtmCyaKoWNjSbOBsbHkdW2GyLPMVFasSIqrw8NJhhoebr3H/PXX73xqZuvWZPqEJUuSDFerry+ZXsR2FKCIECZq0xO7Y+vW5PVE0i/kM9Ie8BMXMG2NrVyw7oJJCXuiYDq2aYwgGNs0xsqvr9z+nzfPOtq14rkrWPOqNQzPG0aI4XnDkwq2jQqu3/71tycl/azteNbez2r42c/a+1nbj+63LtmXBwbPY2vfRlCwtW8jDwyetz3p78fHYGzyd7PVgm1WnFnzO6VX4syjpaKtpCHgOmA0Im6omf5vwBkR8e+SBoB7gQUxxcpnrGibpxhahpYEeQqyWXGWYDuKCCFrVxTyGTl6wGcVTMvQRz5PwbWd7Vi58W18+T/u5qGXX5ck+/plti1g4eOfBXaM2PnUP5w7rW3pRHuGIpQtzhkv2krql3QLcB9wdW2yTx0A3A0QEVuATcDeDdazUtI6Ses2btz5y1SIPMXQMrQkyFOQzYqzBNtRRAhZu6KQz8jRAz6rYNorfeTb2Y6Jc/db9bvGy9RM33XkNVx88SXce++9MxJnWQrYvRJnHrkSfkRsjYgXAAuBwyU9p26RRocdOx3dR8SaiBiJiJEFCxa0Hm0eeYqhZWhJkKcgmxVnCbajiBCydkUhn5HRsgCyC6Z51lEG090OhbaPzOmPfRouUzt9YsTO2ed8eEbiLEMBO08cZYkzj5ZG6UTEQ8C1wNF1szYABwKkp3TmAQ8UEF/r8hRUy9CSIE9BNivOEmxHESFk7YpCPiNHD/isgmnePvIzKavgCtPfDt0ysH0EzvwtJ6LYZfL82IX5W06cNK2do/xOtGcoQq/EmUvWpbjAAmB++nw34AfAsXXLvA24MH1+AvDlrPXOaGuFIloWdEKeGLK2pQStFYoIYdmyyW39l9Vd6V/EjyurB3yeZYpoe5C1TNb8PG0Rsrajfv6h73lu7H3Ea2L4vVduf+z9/lOj/7QFwemK/tMWxN7vP3XS/O3LHfGaWPWOU6be+U20uy861XqhLHFEtNdaIU/Cfx5wM3Ar8FPgtHT6WcBx6fNdgX8C7gR+DPxR1np7+gYoVqisH0enflyduOlHWW8csnDRcJCchp3WY+Gi4Wns8fZU9QYp7ST8arZWKMHoFtuhLIOROnHTD984pDhV2c56bq3QqhKMbrEdyjIYqRM3/fCNQ4pTle0sUjUTfglGt9gOZRmM1O5ojDyjNXzjkOJUZTuLVM2EX4LRLbbD6tUwODh52uDg5MFIWV0ooP32C3lGY/TV/Zfpo2/S/MG+yRsy2Dc4abRG1jJZnwHZl/EXNWqk7O0C8m5nJ7aj7PtqQjUTfhGtEaxQUvPXebpQfOpTD/LGN25uq/1CVluD6++6nm1sm/SebWzj+rt2BKK6Dal/nbVM1mfkuYw/azvy6IV2AXm2sxPb0Qv7akI1i7ZWKllF2TxdKPacez+PPrLTxd2FFnazWisUUbQt4jOKMFsKop3YjlnXWsFsJmUVZbNaL4yPj/PoI3u1tO7pyGqtUETRtojPKMJsKYh2Yjt6aV854VvXZRVls1ovfPBDH6Rv19+0tO7pyGqtUETRtojPKMJsKYh2Yjt6aV854VvXe+qvXg1z5kyeNmfOjqLsVK0Xkna+F/PU154Ldee+J9bdiqmKb1mtFfIUEVcvW82c/skbO6d/Tu72DZ26jL+n2gVMoRPb0Uv7ygm/6krQUx+Sj272+vzzk/u2TxzR9/fvuI/7Bz/0Qeb98Tzu/85f0aiH3znn5I8hq/h2/ivPZ3RkdPvRdr/6GR0Z5fxXJjeUz1ssra+b1b5esmhJw1E6SxYtaekz2tWpz5lpndiOXtpXLtpWXQmuOp5uCOPj4xx0yEEceNaB/OJdd9C4aevOv0yaxlGCAt9sKZbazHHR1qavBFcdTzeEiaP7wfmDUy+YN44SFPh6qQBovccJv+pKcNXxdEKYOHc/9+i5GWvP/xdsGQp8vVQAtN7jhF91JbjqeDoh1B/dDz7tv9g5uQd77dV49E7DOEpQ4OulAqD1Hif8quvQVcdTDQTKE0Lt+xcu3MJFF22edHR/8DnH0zf/Xmq79mruPTyx7ZDcN+fIe+VmO5fQZ31GLxUAbYdeaa3goq3NuImBQJs375g2NJT/90qj99O3mYVvOZP5f3wVAA/98Bh+c/EZxBO7bV9Ecx5j7iGn8oalfZz3ifPa3450FM/mJ3cEMjQ45IRccZ3+XrRTtHXCtxnX7kCgZu8f3PseDv77lwPwi1P/jSfvf9pOywzs9Rt22XYwd/78Tvbbb7+W4t4pDo+gsQbcWsGsRrsDgZot9+T9+zV8XmvLg/sz96i5fPBDH8z3YVPF4RE01kAvfS+c8G3GtTsQqNlyg3vf2/B5/TJzj57LxZdcPK0bbU+KwyNorIFe+l5kJnxJB0r6rqQ7JN0u6ZQGyyyVtEnSLenjtJkJt4LabXvQ5bYJkN06AaYOs1G/fPqfYN/jP7H95b7HfwLNeWzSIprzGPse/wkG5w8WcpRf1AiaVauSDqBS8u+qVW2FNS29UmTsBT01sirrprfA/sCL0ud7Av8JHFq3zFLgylZuptvVm5j3inbv3l2Sm7WvXRsxODg5jMHB/DcpX7s2Ys6cyfPhDwGvr7uZ9usDfh2wNf138vyFwwvb35Zb18bwx4dDZyiGPz7c8g2zR0frtyN5jI62HVpuVb3590xq93vRCjp5E3NJ/wKcFxFX10xbCvxNRBybdz0u2uYwU9XODt+svd2blJdkMwqRp7f/THPxubd1bJSOpMXA94HnRMTDNdOXAl8BNgD3kCT/2xu8fyWwEmDRokWHjTX6X2w79PU1bgQjwbadO0MW/v6CZIXR7vxe0uAGWNt1asBc35l9RIMrkIXYdnqP7dAK6sgoHUl7kCT1d9Um+9RNwHBEPB/4JPC1RuuIiDURMRIRIwsWLJhOvNUyU9XODt+svd2blJdkMwqR1du/E3qpyGjFypXwJQ2SJPvLIuKf6+dHxMMR8Wj6/CpgUNI+hUZaRe22PShB24Q8YbQ7v5dM1du/U3qqyGjFyjrJT9Jz9lLg3CmW2Y8dp4cOB+6aeN3s4aJtTqOjEf39SWWvv7/16t7atRHDwxFS8m+HC7YTli2bXKRctmzy/KwwS7IZhWj3R1qEThYZrVjMZNFW0p8APwBuY8cthd4PLEp/YVwo6e3AKLAFeAx4d0T8cKr1umibQ7s9CUpi1Sq44IKdp0/cxMTM8nNrhdlqlgxPKcPIFLPZwq0VZqsS3JykCI2S/VTTzWxmOOGX2SwZnlKGkSlm5oTfXAlaEuQanlKGODOUYWRKmfTAj8xmq+lWe9t9lHqUTklaEmyPpdnwlDLFOYW1ayP6+iaH2ddXujA7okd+ZFZidLK1QlFKXbTtlWJpj8TZI2F2hPeFtcujdIrWK9fy90icPRJmR3hfWLs8SqdovVIs7ftc2qIAAAjsSURBVJE4eyTMjvC+sG5ywm+kV67l75E4eyTMjvC+sK6a7sn/dh+lLtpG9M61/D0SZ4+E2ZFOFr2yL6yccNHWrH3ttoCYJZ0wrORctDUrQLstIDwCxzrBRVuzArTbAmKWdMKwWcwJ3yzVbgsIj8CxsnPCN0u12wLCI3Cs7JzwzVLnn58UaCeO6Pv7W+vZv2JFUqAdHk4upBoedsHWysVFWzOzHuKirZmZZXLCNzOriMyEL+lASd+VdIek2yWd0mAZSfoHSXdKulXSi2YmXNuJm6ubWU4DOZbZApwaETdJ2hO4UdLVEfGzmmVeATwzfRwBXJD+azOp/tLOsbEdQ0pcKTSzOplH+BExHhE3pc8fAe4ADqhb7NXApWmrhx8B8yXtX3i0NtkHPjD5On5IXn/gA92Jx8xKraVz+JIWAy8EbqibdQBwd83rDez8SwFJKyWtk7Ru48aNrUVqO/OlnWbWgtwJX9IewFeAd0XEw/WzG7xlp/GeEbEmIkYiYmTBggWtRWo786WdZtaCXAlf0iBJsr8sIv65wSIbgANrXi8E7mk/PJuSL+00sxbkGaUj4DPAHRHxsSaLXQGcmI7WORLYFBHjBcZpjfjSTjNrQZ5ROkuANwK3SbolnfZ+YBFARFwIXAUcA9wJbAZOLj5Ua2jFCid4M8slM+FHxHU0Pkdfu0wAbysqKDMzK56vtDUzqwgnfDOzinDCNzOrCCd8M7OKcMI3M6sIJ3wzs4pwwjczqwgnfDOzinDCNzOrCCd8M7OKcMI3M6sIJ3wzs4pwwjczqwgnfDOzinDCNzOrCCd8M7OKcMI3M6sIJ3wzs4rIcxPzf5R0n6SfNpm/VNImSbekj9OKD9PMzNqV5ybmFwPnAZdOscwPIuLYQiIyM7MZkXmEHxHfBx7oQCxmZjaDijqHf5Skn0j6V0nPLmidZmZWoDyndLLcBAxHxKOSjgG+Bjyz0YKSVgIrARYtWlTAR5uZWV5tH+FHxMMR8Wj6/CpgUNI+TZZdExEjETGyYMGCdj/azMxa0HbCl7SfJKXPD0/XeX+76zUzs2JlntKR9AVgKbCPpA3A6cAgQERcCLwWGJW0BXgMOCEiYsYiNjOzaclM+BHx+oz555EM2zQzsxLzlbZmZhXhhG9mVhFO+GZmFeGEb2ZWEU74ZmYV4YRvZlYRTvhmZhXhhG9mVhFO+GZmFeGEb2ZWEU74ZmYV4YRvZlYRTvhmZhXhhG9mVhFO+GZmFeGEb2ZWEU74ZmYV4YRvZlYRTvhmZhWRmfAl/aOk+yT9tMl8SfoHSXdKulXSi4oP08zM2pXnCP9i4Ogp5r8CeGb6WAlc0H5YZmZWtMyEHxHfBx6YYpFXA5dG4kfAfEn7FxWgmZkVY6CAdRwA3F3zekM6bbx+QUkrSf4KAHi82WmiktkH+F23g8jBcRarF+LshRjBcRbt4Om+sYiErwbTotGCEbEGWAMgaV1EjBTw+TPKcRbLcRanF2IEx1k0Seum+94iRulsAA6seb0QuKeA9ZqZWYGKSPhXACemo3WOBDZFxE6nc8zMrLsyT+lI+gKwFNhH0gbgdGAQICIuBK4CjgHuBDYDJ+f87DXTiLcbHGexHGdxeiFGcJxFm3acimh4ut3MzGYZX2lrZlYRTvhmZhXRkYQvqV/SzZKubDBvF0lfSlsz3CBpcSdiaiQjzpMkbZR0S/p4S5diXC/ptjSGnYZnlaXVRY44l0raVLM/T+tCjPMlXS7p55LukHRU3fyy7MusOMuwLw+u+fxbJD0s6V11y3R9f+aMs+v7M43jryXdLumnkr4gade6+S3nziLG4edxCnAHMLfBvDcDD0bEQZJOAD4CvK5DcdWbKk6AL0XE2zsYTzMviYhmF4jUtro4gqTVxRGdCqzOVHEC/CAiju1YNDv7BPDNiHitpDnAUN38suzLrDihy/syIn4BvACSAyfgN8BX6xbr+v7MGSd0eX9KOgB4J3BoRDwm6cvACSStbia0nDtn/Ahf0kLglcCnmyzyauCS9PnlwDJJjS7mmlE54uwVbnWRg6S5wIuBzwBExBMR8VDdYl3flznjLJtlwC8jYqxuetf3Z51mcZbFALCbpAGSX/L11ze1nDs7cUrnXOA9wLYm87e3ZoiILcAmYO8OxFUvK06A49M/RS+XdOAUy82kAL4l6UYlrSrqNWt10WlZcQIcJeknkv5V0rM7GRzwR8BG4LPpabxPS9q9bpky7Ms8cUJ392W9E4AvNJhehv1Zq1mc0OX9GRG/Af4OuIukTc2miPhW3WIt584ZTfiSjgXui4gbp1qswbSOjhXNGefXgcUR8TzgGnb8Zu20JRHxIpI/j98m6cV187u+P1NZcd4EDEfE84FPAl/rcHwDwIuACyLihcDvgf9dt0wZ9mWeOLu9L7dLTzkdB/xTo9kNpnVlXHhGnF3fn5L2IjmCfzrwNGB3SW+oX6zBW6fcnzN9hL8EOE7SeuCLwEslra1bZntrhvRPl3lM3Z1zJmTGGRH3R8Tj6cuLgMM6G+L2OO5J/72P5Nzj4XWLlKLVRVacEfFwRDyaPr8KGJS0TwdD3ABsiIgb0teXkyTW+mW6vS8z4yzBvqz1CuCmiPhtg3ll2J8TmsZZkv25HPh1RGyMiCeBfwb+uG6ZlnPnjCb8iHhfRCyMiMUkfz59JyLqf0tdAbwpff7adJmO/tbPE2fducbjSIq7HSVpd0l7TjwH/hyo7zja9VYXeeKUtN/E+UZJh5N8F+/vVIwRcS9wt6SJzoPLgJ/VLdb1fZknzm7vyzqvp/lpkq7vzxpN4yzJ/rwLOFLSUBrLMnbOOS3nzk6N0plE0lnAuoi4gqQY9TlJd5L8djqhGzE1UhfnOyUdB2whifOkLoS0L/DV9Ls4AHw+Ir4p6a3QdquLTsf5WmBU0hbgMeCETv+iB94BXJb+ef8r4OQS7ss8cZZhXyJpCHgZ8Fc100q3P3PE2fX9GRE3SLqc5PTSFuBmYE27udOtFczMKsJX2pqZVYQTvplZRTjhm5lVhBO+mVlFOOGbmVWEE76ZWUU44ZuZVcT/B2KUAh0mKiXYAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# visualize result\n",
    "\n",
    "cat1 = data[gt_labels__ == 0]\n",
    "cat2 = data[gt_labels__ == 1]\n",
    "cat3 = data[gt_labels__ == 2]\n",
    "\n",
    "for ix, p in enumerate(centers__):\n",
    "    plt.scatter(p[0], p[1], color='C{}'.format(ix), marker='^', edgecolor='black', s=256)\n",
    "        \n",
    "plt.scatter(cat1_[:,0], cat1_[:,1], color='green')\n",
    "plt.scatter(cat2_[:,0], cat2_[:,1], color='red')\n",
    "plt.scatter(cat3_[:,0], cat3_[:,1], color='blue')\n",
    "plt.title('kmeans using sklearn with k=3')\n",
    "plt.xlim(4, 8)\n",
    "plt.ylim(1, 5)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "u5XVOLGBKC4A"
   },
   "source": [
    "#### 寻找 K 值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 281
    },
    "colab_type": "code",
    "id": "uCe9-EHaJrFz",
    "outputId": "4c2fe667-ee92-4909-c582-6605bd862ecc"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEICAYAAABRSj9aAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3de3Rc5Xnv8e8jaXS1LEuyLsaSjA0GbJmLsTABGgcCtkzJAdJwTxqSE0pIoU2bnp6TnOQ0DV1N09DTNm1oEm45SUlCgDQpaQmCEMBJuVnmasnGGGMs2dbFlixblmSNpef8MdvOWJbtkSV5j2Z+n7Vmafbsd8888pJ/e8+73/1uc3dERCR1ZYRdgIiITC4FvYhIilPQi4ikOAW9iEiKU9CLiKQ4Bb2ISIpT0IsAZvZRM3vyKOsvNrPWMbzfs2Z2y8RUJzI+CnqZcsxss5ldFrd8g5l1m9kHjvc93f0H7r4i7j3dzE4db60iyUBBL1Oamd0M3A1c4e7PhV2PSDJS0MuUZWa3Av8XqHf354/Q5jkz+0jw/HeCI/XfDZYvM7PXguefMLPfBM9XBZu/bma9ZnZ93Pv9mZl1mNl2M/tkgnVmmNmXzOy9YNvvm1lRsC7XzB40s51mtsvMVptZRVxNm8xsj5m9a2YfPa5/KEl7CnqZqj4D/BVwqbs3HqXdc8DFwfNlwCbgA3HLh30LcPdlwdOz3X2au/84WK4EioDZwKeAu82sOIFaPxE8LgHmAdOAbwbrbg7esxooBW4D+s2sAPgn4HJ3LwQuBF5L4LNEDqOgl6lqOfAi8OYx2j3HocH+N3HLH2CUoD+KKHCnu0fd/XGgFzg9ge0+Cvy9u29y917gC8ANZpYVvGcpcKq7D7n7GnffHWw3DCwyszx33+7uTWOoVeQgBb1MVbcBpwH3mZkdpd0LwGlBd8g5wPeBajObCSwFVh1l25F2uvv+uOU+Ykfnx3IS8F7c8ntAFlAB/CvQADxkZtvM7OtmFnH3vcD1xH7P7Wb2n2Z2xhhqFTlIQS9TVQdwKfB+4F+O1Mjd+4A1wGeBte4+CDwPfA54x913nIBatwFz4pZrgP1Ae/Dt4CvuvpBY98yHgI8HtTe4+3JgFrAeuPcE1CopSEEvU5a7bwM+CKw0s384StPngDv4bTfNsyOWR9NOrD99IvwI+FMzm2tm04CvAj929/1mdomZnWlmmcBuYl05Q2ZWYWZXBn31+4h1Ew1NUD2SZhT0MqW5ewuxsL/GzP7mCM2eAwr5bTfNyOXR/CXwvWAkzHXjLPMBYl00q4B3gQHgj4J1lcCjxEJ+XVDbg8T+b/4ZsW8DXcTOJ/zhOOuQNGW68YiISGrTEb2ISIpT0IuIpDgFvYhIilPQi4ikuKxEGpnZSuAbQCZwn7t/bcT624DbiQ3/6gVudffmYN0XiF0uPgT8sbs3HO2zZs6c6SeffPIYfw0RkfS2Zs2aHe5eNtq6Y466Ccb3biB2yXkrsBq48UCQB22mH7hs28yuBP7Q3Vea2UJiY4iXErs68JfAae5+xPHAdXV13th4tKlLRERkJDNb4+51o61LpOtmKbAxmKdjEHgIuCq+QdzcHAAFwIG9x1XAQ+6+z93fBTYG7yciIidIIl03s4GWuOVW4PyRjczsdmKXlWcTu4DlwLYvjth29ijb3grcClBTU5NI3SIikqBEjuhHmzDqsP4ed7/b3U8B/hfwpTFue4+717l7XVnZqF1MIiJynBIJ+lZic2UfUEXssuwjeQi4+ji3FRGRCZZI0K8G5gcTMmUDNwCPxTcws/lxi1cAbwfPHyM273aOmc0F5gMvj79sERFJ1DH76IMZ9u4gNmd2JvCAuzeZ2Z1Ao7s/BtwR3Kw5CnQTu2sOQbuHgWZi07LefrQRNyIiMvGSblIzDa8UERm78Q6vnBJ29Q3yjV++TfO23cduLCKSRhK6MnYqMDP++Vdv0xfdz8KTpoddjohI0kiZI/qivAgXnFJKw9o2kq07SkQkTCkT9AArF1WyeWcfG9p7wy5FRCRppFTQL19YgRk8sbYt7FJERJJGSgV9eWEuS2qKaWhS0IuIHJBSQQ9QX1tJ8/bdtHT1hV2KiEhSSMmgB3RULyISSLmgrynNZ8Gs6eqnFxEJpFzQA9TXVrBmSzcdewbCLkVEJHQpGfQrF1XiDk81t4ddiohI6FIy6E+vKGROaT4NTQp6EZGUDHozY2VtJS+8s4Oe/mjY5YiIhColgx5gRW0l0SHnmfUdYZciIhKqlA36xdUzKC/M0TBLEUl7KRv0GRnGitoKnn2rk4Go7nUiIukrZYMeYGXtLPqjQ6za0Bl2KSIioUnpoD9/XglFeRGeUPeNiKSxlA76SGYGly4o5+l1HUSHhsMuR0QkFCkd9BCb+6anP8pLm7rCLkVEJBQpH/TL5peRG8nQ6BsRSVspH/R52ZlcfFo5DU1tDA/rFoMikn5SPugB6hdV0LFnH6+17gq7FBGREy4tgv6DZ1SQlWHqvhGRtJQWQV+UF+GCU0ppWNuGu7pvRCS9pEXQQ2zq4s07+9jQ3ht2KSIiJ1TaBP3yhRWYoTtPiUjaSZugLy/MZUlNsfrpRSTtJBT0ZrbSzN4ys41m9vlR1n/OzJrN7A0ze9rM5sStGzKz14LHYxNZ/FjV11bSvH03LV19YZYhInJCHTPozSwTuBu4HFgI3GhmC0c0exWoc/ezgEeBr8et63f3c4LHlRNU93Gpr60E0FG9iKSVRI7olwIb3X2Tuw8CDwFXxTdw92fc/cBh8otA1cSWOTFqSvNZMGu6+ulFJK0kEvSzgZa45dbgtSP5FPCLuOVcM2s0sxfN7OrRNjCzW4M2jZ2dkzul8MraStZs6aZjz8Ckfo6ISLJIJOhtlNdGHYxuZh8D6oC74l6ucfc64CbgH83slMPezP0ed69z97qysrIESjp+9YsqcIenmnXjcBFJD4kEfStQHbdcBWwb2cjMLgO+CFzp7vsOvO7u24Kfm4BngcXjqHfcTq8oZE5pPg1NCnoRSQ+JBP1qYL6ZzTWzbOAG4JDRM2a2GPgOsZDviHu92MxyguczgYuA5okq/niYGStrK3nhnR309EfDLEVE5IQ4ZtC7+37gDqABWAc87O5NZnanmR0YRXMXMA14ZMQwygVAo5m9DjwDfM3dQw16gBW1lUSHnGfWdxy7sYjIFJeVSCN3fxx4fMRrfxH3/LIjbPc8cOZ4CpwMi6tnUF6YQ0NTG1cvPtp5ZRGRqS9troyNl5FhrKit4Nm3OhmIDoVdjojIpErLoAdYWTuL/ugQqzZM7nBOEZGwpW3Qnz+vhKK8CE/oKlkRSXFpG/SRzAwuXVDO0+s6iA4Nh12OiMikSdugh9jcNz39UV7a1BV2KSIikyatg37Z/DLyIpma5ExEUlpaB31ediYfOK2MhqY2hod1i0ERSU1pHfQQu8Vgx559vNa6K+xSREQmRdoH/SVnlJOVYTRo6mIRSVFpH/RFeREuOKWUhqY23NV9IyKpJ+2DHmLdN5t39rGhvTfsUkREJpyCHli+sAIzdOcpEUlJCnqgvDCXJTXFGmYpIilJQR+or62keftuWrr6jt1YRGQKUdAH6msrAXRULyIpR0EfqCnNZ8Gs6eqnF5GUo6CPs7K2kjVbuunYMxB2KSIiE0ZBH6d+UQXu8FSzbhwuIqlDQR/n9IpCTi7Np6FJQS8iqUNBH8fMqK+t5PmNO+jpj4ZdjojIhFDQj1C/qJL9w84z6zvCLkVEZEIo6Ec4p2oG5YU5GmYpIilDQT9CRoaxoraCZ9/qZCA6FHY5IiLjpqAfxcraWfRHh1i1oTPsUkRExk1BP4rz55VQlBfhCXXfiEgKUNCPIpKZwaULynl6XQfRoeGwyxERGRcF/RHU11bS0x/lpU1dYZciIjIuCvojWDa/jLxIpkbfiMiUl1DQm9lKM3vLzDaa2edHWf85M2s2szfM7GkzmxO37mYzezt43DyRxU+mvOxMPnBaGQ1NbQwP6xaDIjJ1HTPozSwTuBu4HFgI3GhmC0c0exWoc/ezgEeBrwfblgBfBs4HlgJfNrPiiSt/cq1cVEnHnn281ror7FJERI5bIkf0S4GN7r7J3QeBh4Cr4hu4+zPufuCOHS8CVcHzeuApd+9y927gKWDlxJQ++S45o5ysDKNBUxeLyBSWSNDPBlrilluD147kU8AvxrKtmd1qZo1m1tjZmTxj14vyIlx46kwamtpwV/eNiExNiQS9jfLaqKlnZh8D6oC7xrKtu9/j7nXuXldWVpZASSdOfW0Fm3f2saG9N+xSRESOSyJB3wpUxy1XAdtGNjKzy4AvAle6+76xbJvMli+swAzdeUpEpqxEgn41MN/M5ppZNnAD8Fh8AzNbDHyHWMjHT/vYAKwws+LgJOyK4LUpo7wwlyU1xRpmKSJT1jGD3t33A3cQC+h1wMPu3mRmd5rZlUGzu4BpwCNm9pqZPRZs2wX8FbGdxWrgzuC1KaW+tpLm7btp6eo7dmMRkSRjyXaSsa6uzhsbG8Mu4xBbdvax7K5n+NIVC7jl/fPCLkdE5DBmtsbd60ZbpytjE1BTms+CWdPVTy8iU5KCPkEraytZs6Wbjj0DYZciIjImCvoE1S+qwB2eataNw0VkalHQJ+j0ikJOLs2noUlBLyJTi4I+QWZGfW0lz2/cQU9/NOxyREQSpqAfg/pFlewfdp5Z33HsxiIiSUJBPwbnVM2gvDBHF0+JyJSioB+DjIxY982zb3UyEB0KuxwRkYQo6MeovraS/ugQqzYkzyybIiJHo6Afo/PnlVCUF+EJdd+IyBShoB+jSGYGly4o5+l1HUSHhsMuR0TkmBT0x6G+tpKe/igvbZpy87OJSBpS0B+HZfPLyItkavSNiEwJCvrjkJedyQdOK6OhqY3h4eSa/VNEZCQF/XFauaiSjj37eK11V9iliIgclYL+OF1yRjlZGUaDpi4WkSSnoD9ORXkRLjx1Jg1NbSTbzVtEROIp6MehvraCzTv72NDeG3YpIiJHpKAfh+ULKzBDd54SkaSmoB+H8sJcltQUa5iliCQ1Bf04rVxUSfP23bR09YVdiojIqBT041RfWwmgo3oRSVoK+nGqLsln4azp6qcXkaSloJ8A9bWVrNnSTceegbBLERE5jIJ+AtQvqsAdnmrWjcNFJPko6CfA6RWFnFyaT0OTgl5Eko+CfgKYxW4x+PzGHfT0R8MuR0TkEAr6CVK/qJL9w84z6zvCLkVE5BAJBb2ZrTSzt8xso5l9fpT1y8zsFTPbb2bXjFg3ZGavBY/HJqrwZHNO1QzKC3M0zFJEkk7WsRqYWSZwN7AcaAVWm9lj7t4c12wL8Angf4zyFv3ufs4E1JrUMjJi3TePrmllIDpEbiQz7JJERIDEjuiXAhvdfZO7DwIPAVfFN3D3ze7+BpDWN1Gtr62kPzrEqg2dYZciInJQIkE/G2iJW24NXktUrpk1mtmLZnb1aA3M7NagTWNn59QNyfPnlVCUF+EJdd+ISBJJJOhtlNfGMgF7jbvXATcB/2hmpxz2Zu73uHudu9eVlZWN4a2TSyQzg0sXlPP0ug6iQ2n95UZEkkgiQd8KVMctVwHbEv0Ad98W/NwEPAssHkN9U87K2kp6+qO8tKkr7FJERIDEgn41MN/M5ppZNnADkNDoGTMrNrOc4PlM4CKg+ehbTW3LTisjL5Kp0TcikjSOGfTuvh+4A2gA1gEPu3uTmd1pZlcCmNl5ZtYKXAt8x8yags0XAI1m9jrwDPC1EaN1Uk5uJJOLTy+joamN4WHdYlBEwnfM4ZUA7v448PiI1/4i7vlqYl06I7d7HjhznDVOOfW1lfxibRuvte7i3JrisMsRkTSnK2MnwSVnlJOVYTRo6mIRSQIK+klQlBfhwlNn0tDUhru6b0QkXAr6SVJfW8HmnX1saO8NuxQRSXMK+kmyfGEFZujOUyISOgX9JCkvzGVJTbGGWYpI6BT0k2jlokqat++mpasv7FJEJI0p6CdRfW0lgI7qRSRUCvpJVF2Sz8JZ09VPLyKhUtBPsvraStZs6aZjz0DYpYhImlLQT7KViypxh3tXbdKYehEJhYJ+kp1WMY1rl1Rx76/f5Ss/b9b8NyJywiU0140cPzPjbz9yFtPzItz/m3fZ1TfIXdeeTSRT+1gROTEU9CdARobxpSsWUFKQzV0Nb7GrP8q3PrqEvGzdV1ZEJp8OK08QM+P2S07lqx8+k1UbOvnY/S/R0xcNuywRSQMK+hPspvNruPumc3mztYfrvvMC7bs1GkdEJpeCPgSXnzmL737yPFq7+/jIt55n8469YZckIilMQR+Si06dyQ//4H3s3befa779PGu39oRdkoikKAV9iM6unsEjt11IdmYGN97zIi9t2hl2SSKSghT0ITu1fBqPfuZCyqfn8PEHXuap5vawSxKRFKOgTwInzcjjkdsu5IzKQm57cA2PNLaEXZKIpBAFfZIoKcjmB3/wPi6YV8qfP/oG967aFHZJIpIiFPRJZFpOFvd/oo4rzpzFXz++jq/9Yr3mxxGRcdOVsUkmJyuTf7pxMUX5Eb793Dt07x3krz+8iCxNmSAix0lBn4QyM4y/vnoRpQXZ/POvNrKrf5Bv3LCY3IimTBCRsdNhYpIyM/5sxen8xYcW0tDUzie/u5o9A5oyQUTGTkGf5P7778zlH64/m5c3d3HTvS+xo3df2CWJyBSjoJ8CPry4ins/voQN7Xu47tsv0Nqtm42LSOIU9FPEB8+o4MFbzmdH7z6u+dYLvN2+J+ySRGSKSCjozWylmb1lZhvN7POjrF9mZq+Y2X4zu2bEupvN7O3gcfNEFZ6Ozju5hB9/+gKG3Ln2Oy/wypbusEsSkSngmEFvZpnA3cDlwELgRjNbOKLZFuATwA9HbFsCfBk4H1gKfNnMisdfdvpaMGs6P7ntQqbnRvjovS/x3IbOsEsSkSSXyBH9UmCju29y90HgIeCq+Abuvtnd3wCGR2xbDzzl7l3u3g08BaycgLrTWk1pPo9+5gJOnlnALd9bzc9f3xZ2SSKSxBIJ+tlA/OQrrcFriRjPtnIU5YW5PHTr+1hcXcwfP/Qq//rC5rBLEpEklUjQ2yivJXpdfkLbmtmtZtZoZo2dneqKSFRRXoTvf2opl55Rzv/59ya+8cu3NWWCiBwmkaBvBarjlquARPsKEtrW3e9x9zp3rysrK0vwrQUgN5LJtz62hN87dzb/8MsNfOXnzQwPK+xF5LcSmQJhNTDfzOYCW4EbgJsSfP8G4KtxJ2BXAF8Yc5VyVJHMDP7umrMpyc/mvt+8S3ffIH937dlEND+OiJBA0Lv7fjO7g1hoZwIPuHuTmd0JNLr7Y2Z2HvBToBj4b2b2FXevdfcuM/srYjsLgDvdvWuSfpe0lpFhfPGKBZRMy+brT7xFT3+Uf/noueRnazojkXRnydanW1dX542NjWGXMaX96OUtfPGnb3JO9Qwe+MR5zMjPDrskEZlkZrbG3etGW6fv9inoxqU13H3Tuazdupvrv/Mi7bsHwi5JREKkoE9Rl585i+9+8jxau/v4yLee590de8MuSURCoqBPYRedOpMf3fo++gaHuPbbz7N2a0/YJYlICBT0Ke6sqhk8/OkLyM7M4MZ7XuTFTTvDLklETjAFfRo4tXwaj37mQiqKcvn4Ay/zVHN72CWJyAmkoE8TJ83I45FPX8CCWdO57cE1PNLYcuyNRCQlKOjTSHFBNj+85XwuPKWUP3/0De5Z9U7YJYnICaCgTzMFOVncd3MdV5w5i68+vp7fv/8l/vON7ezbPxR2aSIySXTZZBrKycrkn25czMKTpvPgi+9x+w9foTg/wtWLZ3NdXTULZk0Pu0QRmUC6MjbNDQ07v367k0caW3myuY3okHNWVRHX1lVz5dknUZQXCbtEEUnA0a6MVdDLQV17B/nZq1t5uLGF9W17yMnK4PJFlVxXV8375pWSkTHarNMikgwU9DIm7s7arbv5ceMW/v21bewZ2E91SR7XLqnmI0uqmD0jL+wSRWQEBb0ct4HoEA1NbTzc2MJ/bdyJGbx/fhnX1VWxfGEFOVmZYZcoIijoZYK0dPXxyJpWHm1sYVvPADPyI1x9TuwE7sKTdAJXJEwKeplQQ8POf23cwcONLTzZ1M7g0DBnzi7iuroqrjx7NkX5OoErcqIp6GXS7OqLncD9cWMr67bvJjsrg5W1lVx/XjUX6ASuyAmjoJcTYu3WHh5ubOFnr25l98B+qopjJ3CvqdMJXJHJpqCXE2ogOsSTze08vLqF/3pnBwC/c+pMrqurZvnCCnIjOoErMtEU9BKalq4+fvJKK480trJ1Vz9FeRE+vHg219ZVUXtSUdjliaQMBb2EbnjYef6dnTzc2MITTW0M7h+m9qTpXFdXzdXn6ASuyHgp6CWp7Oob5LHXt/FwYwtrt8ZO4NbXVnJ9XTUXnqITuCLHQ0EvSatpWw+PNLby01e30tMfZfaMPK5ZUsXVi2czd2ZB2OWJTBkKekl6A9EhfrmunR+vbuE3G3fgDvPLp1FfW8mK2grOnF2EmY70RY5EQS9TyvaefhrWtvFkczsvvdvF0LAzqyiXFQsrqK+t5Ly5JUQydSsFkXgKepmyuvcO8vT6Dp5samPV250MRIcpyotw6YJy6msrWTa/jLxsDdcUUdBLSugfHGLV2500NLXx9LoOevqj5EYyWDa/jBW1lVx6RjnFBdlhlykSiqMFve4wJVNGXnYm9bWV1NdWEh0aZvW7XTQ0xbp4nmxuJzPDWHpyCfW1FSyvrdTVuCIBHdHLlOfuvLm1hyeb2mloauPtjl4AzpxdFOvXX1TJ/PJpOpkrKU1dN5JWNnX2xo7ym9p4ZcsuAObOLGDFwgpW1FayuHqGxupLyhl30JvZSuAbQCZwn7t/bcT6HOD7wBJgJ3C9u282s5OBdcBbQdMX3f22o32Wgl4mUsfugYNdOy+8s4PokFNWmMPyhRWsWFjBhafMJDtLI3hk6htX0JtZJrABWA60AquBG929Oa7NHwJnufttZnYD8GF3vz4I+v9w90WJFqugl8nS0x/l2bc6eLKpnWff6mDv4BCFOVlcfEY59bUVXHx6OdNydNpKpqbxnoxdCmx0903Bmz0EXAU0x7W5CvjL4PmjwDdNHaKSZIryIlx1zmyuOmc2A9Ehnn9nBw1r2/nlunZ+/vo2sjMzuOjUUuprK7l0QQVlhTlhlywyIRIJ+tlAS9xyK3D+kdq4+34z6wFKg3VzzexVYDfwJXf/9cgPMLNbgVsBampqxvQLiByP3EgmHzyjgg+eUcHQsLPmvW6ebGqjobmNZ/7tTczepG5OMSsWxkb51JTmh12yyHFLpOvmWqDe3W8Jln8fWOrufxTXpilo0xosv0Psm0AvMM3dd5rZEuBnQK277z7S56nrRsLk7qxv20NDUxsNTe2s2x77Uz2jspAVtZUsmVPMnJJ8Zhfn6epcSSrj7bppBarjlquAbUdo02pmWUAR0OWxvcg+AHdfE+wATgOU5JKUzIwFs6azYNZ0/uSy02jp6js4Vv+bv3qb4eC4KDPDOGlGLnNKCqgpzWdOST5zSvOpKSlgTmk+BerrlySSyF/jamC+mc0FtgI3ADeNaPMYcDPwAnAN8Ct3dzMrIxb4Q2Y2D5gPbJqw6kUmWXVJPre8fx63vH8e3XsHebujl/d27mVLVx/v7ezjva4+fvHmdrr7oodsN3NaNjUl+cwpLQh+/nZHMHNatsb0ywl1zKAP+tzvABqIDa98wN2bzOxOoNHdHwPuB/7VzDYCXcR2BgDLgDvNbD8wBNzm7l2T8YuITLbigmyWzi1h6dySw9btHoiyZeeB8N978PnL73bxs9e2Et9DWpCdSfXB8I/bEZQUcNKMXLLUJSQTTBdMiUyyffuHaO3uD8J/L+919cWed/WxpauPwf3DB9tmZRizi/MOCf+ag98G8snPVpeQjE5z3YiEKCcrk1PKpnFK2bTD1g0PO+17Bnhv54Hw3xt73tXHz1/fTk//oV1CZYU5zCnJD84LxM4H1AQ7gdICdQnJ6BT0IiHKyDBmFeUxqyiP980rPWx9T1/0kPB/b2fs+Qvv7OSnrx7aJZQXyaS6JI/q4nyqS/KpKs475Of0XN2XN10p6EWSWFF+hLPyZ3BW1YzD1g1Eh2jtjp0LaOnqo6W7/+DPl9/tYs++/Ye+V17kkB1BdXEeVSX5VBfHdga5Ec3rn6oU9CJTVG4kk1PLCzm1vPCwde5OT3+Ulq5+WroP7Aj6aOnq5632PTy9vuOQcwMA5YU5B3cA1Qd2AMGOYVaRThJPZQp6kRRkZszIz2ZGfjZnVhUdtn542Ons3XfIDuDA89Wbu3ns9W0HrxmA2EniWTNyY98GivNj3wxK8qkKnpdNy9H5gSSmoBdJQxkZRsX0XCqm51J38uHDRaNDw2zfNXDYt4GW7j6eXt/Bjt59h7TPjWTEQj/u20B1SR6VRXnMnJbNzGk56hoKkYJeRA4TycyIjeY5whw//YOx8wMjvw20dPXT+F43ewb2H7bNtJysg6E/c1oOMwuzKS3IYWZhDmVxr5dOy2ZaTpa+IUwgBb2IjFledibzKwqZX3H4+QGIjRZq6e6jrWeAnXv3saN3kM49+9jRG3u809nLS+/uO+yK4gNysjKCnUFsJxDbIcTtJKblHNxpzMiPaKdwDAp6EZlwRfkRivKLWDT78PMD8aJDw3Ttje0Edu4dZEfczmBH7yA7evexddcAr7f20LV3kKHhwy/wzMowSoPQLw12AGUjvzUEz0vys9PypLKCXkRCE8nMOHiu4FiGh53uvsGDO4TOuJ3BzrjnG9v3sKN3kMGh4cPewwxK8rMpKTj8UZyfTem02M/411Ph3IKCXkSmhIwMozQ4aj/tCF1GB7g7e/btD74hDB72LaGrd5CuYJK6rr2DdPcNcqTZYPKzM4+4Eziwg4hfLsqLkJlk9yRW0ItIyjEzpudGmJ4bYV7ZsdsPDTu7+6PsDEJ/Z2/sZ9fe2KN77+DBde90xnYOfYNDo75XhsGM/GyK8yOUFuRQXBA55reGyZ7DSEEvImkvM8MoLsimuCA74W0GokO/3REcYaews3eQd3fsZc17u+juG/0cAwfmc/sAAAS5SURBVMSGp5bkZ3PunGK+edO5E/VrHaSgFxE5DrmRTE6akcdJM/ISaj887OwZ2M/OvfuCHUOUrr376NobPbhTqCyanPsUK+hFRE6AjAwLRiOd+Mnl0m+ckYhImlHQi4ikOAW9iEiKU9CLiKQ4Bb2ISIpT0IuIpDgFvYhIilPQi4ikOPMjzeQTEjPrBN4bx1vMBHZMUDkTSXWNjeoaG9U1NqlY1xx3H3Vmn6QL+vEys0Z3rwu7jpFU19iorrFRXWOTbnWp60ZEJMUp6EVEUlwqBv09YRdwBKprbFTX2KiusUmrulKuj15ERA6Vikf0IiISR0EvIpLiUibozewBM+sws7Vh13KAmVWb2TNmts7Mmszss2HXBGBmuWb2spm9HtT1lbBrimdmmWb2qpn9R9i1HGBmm83sTTN7zcwaw67nADObYWaPmtn64O/sgrBrAjCz04N/qwOP3Wb2J0lQ158Gf/NrzexHZpYbdk0AZvbZoKamyfh3Spk+ejNbBvQC33f3RWHXA2Bms4BZ7v6KmRUCa4Cr3b055LoMKHD3XjOLAL8BPuvuL4ZZ1wFm9jmgDpju7h8Kux6IBT1Q5+5JdZGNmX0P+LW732dm2UC+u+8Ku654ZpYJbAXOd/fxXAw53jpmE/tbX+ju/Wb2MPC4u/+/sGoK6loEPAQsBQaBJ4DPuPvbE/UZKXNE7+6rgK6w64jn7tvd/ZXg+R5gHTA73KrAY3qDxUjwSIo9vplVAVcA94VdS7Izs+nAMuB+AHcfTLaQD1wKvBNmyMfJAvLMLAvIB7aFXA/AAuBFd+9z9/3Ac8CHJ/IDUibok52ZnQwsBl4Kt5KYoHvkNaADeMrdk6Iu4B+B/wkMh13ICA48aWZrzOzWsIsJzAM6ge8GXV33mVlB2EWN4gbgR2EX4e5bgb8DtgDbgR53fzLcqgBYCywzs1Izywd+F6ieyA9Q0J8AZjYN+AnwJ+6+O+x6ANx9yN3PAaqApcHXx1CZ2YeADndfE3Yto7jI3c8FLgduD7oKw5YFnAt8y90XA3uBz4db0qGC7qQrgUeSoJZi4CpgLnASUGBmHwu3KnD3dcDfAk8R67Z5Hdg/kZ+hoJ9kQR/4T4AfuPu/hV3PSMFX/WeBlSGXAnARcGXQH/4Q8EEzezDckmLcfVvwswP4KbH+1LC1Aq1x38YeJRb8yeRy4BV3bw+7EOAy4F1373T3KPBvwIUh1wSAu9/v7ue6+zJiXdAT1j8PCvpJFZz0vB9Y5+5/H3Y9B5hZmZnNCJ7nEfsPsD7cqsDdv+DuVe5+MrGv+79y99CPuMysIDiZTtA1soLY1+1QuXsb0GJmpwcvXQqEeqJ/FDeSBN02gS3A+8wsP/i/eSmx82ahM7Py4GcN8HtM8L9Z1kS+WZjM7EfAxcBMM2sFvuzu94dbFRcBvw+8GfSHA/xvd388xJoAZgHfC0ZDZAAPu3vSDGVMQhXAT2PZQBbwQ3d/ItySDvoj4AdBF8km4JMh13NQ0N+8HPh02LUAuPtLZvYo8AqxrpFXSZ6pEH5iZqVAFLjd3bsn8s1TZniliIiMTl03IiIpTkEvIpLiFPQiIilOQS8ikuIU9CIiKU5BLyKS4hT0IiIp7v8DGgNl2ymEqEoAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "\n",
    "loss = []\n",
    "\n",
    "for i in range(1, 10):\n",
    "    kmeans = KMeans(n_clusters=i, max_iter=100).fit(data)\n",
    "    loss.append(kmeans.inertia_ / len(data) / 3)\n",
    "\n",
    "plt.title('K with loss')\n",
    "plt.plot(range(1, 10), loss)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "oaa4ModGKN4c"
   },
   "source": [
    "##### 例 14.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "87a-GPzLKK62"
   },
   "outputs": [],
   "source": [
    "X = [[0, 2], [0, 0], [1, 0], [5, 0], [5, 2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 107
    },
    "colab_type": "code",
    "id": "NoacPJOONbqE",
    "outputId": "70147d21-d14d-416c-ab26-80b3f23793a2"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 2],\n",
       "       [0, 0],\n",
       "       [1, 0],\n",
       "       [5, 0],\n",
       "       [5, 2]])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.asarray(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "w5CrPk68I9B9"
   },
   "outputs": [],
   "source": [
    "m = MyKmeans(2, 100)\n",
    "points_set, centers = m.fit(np.asarray(X))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 53
    },
    "colab_type": "code",
    "id": "THUOLIKiKkLc",
    "outputId": "693794ef-67b6-4bd4-e1bb-3d05facd10f1"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: [array([0, 2]), array([0, 0]), array([1, 0])],\n",
       " 1: [array([5, 0]), array([5, 2])]}"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "points_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 53
    },
    "colab_type": "code",
    "id": "1TqaAPnnKrkn",
    "outputId": "7bfe9b28-4cda-4a20-ca99-112373a4313c"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 0],\n",
       "       [5, 1]])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "centers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "7f_Jv2EFLmms"
   },
   "outputs": [],
   "source": [
    "kmeans = KMeans(n_clusters=2, max_iter=100).fit(np.asarray(X))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "S5oVNBQdL-sl",
    "outputId": "d04fd98e-8f47-4d8b-cf79-da6a19157843"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 0, 0, 1, 1])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 53
    },
    "colab_type": "code",
    "id": "MG_sSMnHMU_r",
    "outputId": "9c4393a2-3f9e-492e-bd10-98d48ee6495c"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.33333333, 0.66666667],\n",
       "       [5.        , 1.        ]])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans.cluster_centers_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "本章代码来源：https://github.com/hktxt/Learn-Statistical-Learning-Method\n",
    "\n",
    "本文代码更新地址：https://github.com/fengdu78/lihang-code\n",
    "\n",
    "中文注释制作：机器学习初学者公众号：ID:ai-start-com\n",
    "\n",
    "配置环境：python 3.5+\n",
    "\n",
    "代码全部测试通过。\n",
    "![gongzhong](../gongzhong.jpg)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Clustering.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
